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

Question

我想在 JavaScript 中找到所有可能的数组 - 非负整数 - 大小L总和 - 至多 - ：Nfunction 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));