查找总和为 N 或更小的所有可能的 L 大小数组的算法

Question

我想在 JavaScript 中找到所有可能的数组 - 非负整数 - 大小L总和 - 至多 - ：N

function findArrays(size, maxSum){}

输入示例： findArrays(3, 2)

示例输出：

[[0,0,0], [0,0,1], [0,0,2], [0,1,0], [0,1,1], [0,2,0], [1,0,0], [1,0,1], [1,1,0], [2,0,0]]

我尝试了什么：

我想出了这个算法：

• 从左边开始，添加数组成员

• 如果总和等于Nat slot i：

• 如果当前索引处的成员等于N，则将所有索引重置到此处并递增下一个槽

• 否则：重置以前的插槽并增加此插槽

• 否则：

• 增加第一个可用插槽

我的代码：

let getNextArray = (r,L,N)=>{

    let sum=0, ind=0, i;

    for(i=0; i<L; i++){

        sum += r[i];

        if(sum===N){

            ind = i + (r[i]===N?1:0);

            break;

        }

    }

    r[ind]++;

    for(i=0; i<ind; i++){

        r[i]=0;

    }

    return r;

};

let findArrays=(L, N)=>{

    let arrays=[],r=[],i;

    for(i=0; i<L; i++){

        r[i] = 0;

    }

    while(r[L-1]<N){

        r = getNextArray(r,L,N);

        arrays.push(r.slice());

    }

    return arrays;

}

它适用于我的示例输入，但当我调用它时，findArrays(5,3)它会找到一半 (28 / 56) 的答案。即使我让它工作，我怀疑它对于更大的输入是否有效，因为它会计算每轮的总和。我敢肯定有一种我找不到的更聪明的方法来做到这一点..

昨天我问了一个类似的问题，在效率方面有一个很好的答案，但我意识到我需要固定大小的数组。为类似的问题道歉，但也许有一天它会帮助别人 :)

我也可以使用一种方法findArrays(size, sum)并用 sums 迭代它1:N，不幸的是我也不知道该怎么做。

Answer 1

您可以在末尾修改trincot的解决方案filter：

function findArrays(maxSize, maxSum) {

  let arr = [];

  let result = []; // <--- will collect all the subarrays

  function recur(maxSum) {

    let k = arr.length;

    result.push([...arr]);

    if (k === maxSize) return;

    for (let i = 0; i <= maxSum; i++) {

      arr[k] = i;

      recur(maxSum - i);

    }

    arr.length = k;

  }

  recur(maxSum);

  return result.filter(({ length }) => length == maxSize);

}

// demo

for (let arr of findArrays(3, 2))

  console.log(JSON.stringify(arr));

Answer 2

这是递归函数的非生成版本，它将给出您想要的结果。它计算出当前级别 ( 0..maxSum) 的所有可能值，然后将它们附加到数组的所有可能结果中size-1：

const findArrays = (size, maxSum) => {

  let possibles = Array.from({

    length: maxSum + 1

  }, (_, i) => i);

  if (size == 1) return possibles;

  let result = [];

  possibles.forEach(p => {

    findArrays(size - 1, maxSum - p).forEach(a => {

      result.push([p].concat(a));

    });

  });

  return result;

}

console.log(findArrays(3, 2));