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

Question

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

function findArrays(maxSize, maxSum){}

输入示例： findArrays(3, 10)

一些可接受的输出：（不写全部，因为它太长了）

[[0], [0,0,0], [10,0,0], [1,9], [1,2,3] /*, ... */]

到目前为止我尝试了什么：

我知道它看起来像家庭作业，但它不是 :) 我可以想到一个解决方案，它只生成所有 ( size*maxSum) 个可接受大小的可能数组，然后遍历它们以检查总和是否大于maxSum。但是，我认为随着变大，这种解决方案在性能方面非常糟糕maxSum。我正在寻找更有效的实施，但我不知道从哪里开始。

我的“坏”解决方案

function getNextArray(r,maxVal){

    for(var i=r.length-1;i>=0;i--){

        if(r[i]<maxVal){

            r[i]++;

            if(i<r.length-1){

                r[i+1]=0;

            }

            break;

        }

    }

    return r;

}

function getAllArraysOfSize(size, maxVal){

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

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

        r[i]=0;

    }

    while(r.reduce((a, b) => a + b, 0) < (maxVal*size)){

        r = getNextArray(r.slice(),maxVal);

        arrays.push(r);

    }

    return arrays;

};

function findArrays(maxSize, maxSum){

    var allArrays=[],arraysOfFixedSize=[],acceptableArrays=[],i,j;

    for(i=1; i<=maxSize; i++){

        arraysOfFixedSize=getAllArraysOfSize(i,maxSum);

        for(j=0; j<arraysOfFixedSize.length; j++){

            allArrays.push(arraysOfFixedSize[j]);

        }

    }

    for(i=0; i<allArrays.length; i++){

        if(allArrays[i].reduce((a, b) => a + b, 0) <= maxSum){

            acceptableArrays.push(allArrays[i]);

        }

    }

    return acceptableArrays;

};

Answer 1

您可以使用递归和生成器。对于更高价值的参数，输出的数量会快速增长，所以我在这里将它们保持在较低水平：function * findArrays(maxSize, maxSum) {&nbsp; let arr = [];&nbsp;&nbsp;&nbsp; function * recur(maxSum) {&nbsp; &nbsp; let k = arr.length;&nbsp; &nbsp; yield [...arr]; // or: if (k) yield [...arr]&nbsp; &nbsp; if (k === maxSize) return;&nbsp; &nbsp; for (let i = 0; i <= maxSum; i++) {&nbsp; &nbsp; &nbsp; arr[k] = i;&nbsp; &nbsp; &nbsp; yield * recur(maxSum - i);&nbsp; &nbsp; }&nbsp; &nbsp; arr.length = k;&nbsp; }&nbsp;&nbsp;&nbsp; yield * recur(maxSum);&nbsp;&nbsp;}// demofor (let arr of findArrays(2, 4))&nbsp; &nbsp; console.log(JSON.stringify(arr));注意：这也会产生空数组，这是有道理的。如果你想避免这种情况，那么只需检查你不会产生一个空数组。如果您更喜欢使用普通函数而不是生成器，则将最里面的yield表达式转换为push数组result，如下所示：function findArrays(maxSize, maxSum) {&nbsp; let arr = [];&nbsp; let result = []; // <--- will collect all the subarrays&nbsp;&nbsp; function recur(maxSum) {&nbsp; &nbsp; let k = arr.length;&nbsp; &nbsp; result.push([...arr]);&nbsp; &nbsp; if (k === maxSize) return;&nbsp; &nbsp; for (let i = 0; i <= maxSum; i++) {&nbsp; &nbsp; &nbsp; arr[k] = i;&nbsp; &nbsp; &nbsp; recur(maxSum - i);&nbsp; &nbsp; }&nbsp; &nbsp; arr.length = k;&nbsp; }&nbsp;&nbsp;&nbsp; recur(maxSum);&nbsp; return result;}// demofor (let arr of findArrays(2, 4))&nbsp; &nbsp; console.log(JSON.stringify(arr));

Answer 2

我希望这是有帮助的const data = [[0],[0,0,0],[10,0,0],[1,9],[1,2,3]];function findArrays(maxSize, maxSum){&nbsp; return data.reduce(&nbsp; &nbsp; (acc, value) => {&nbsp; &nbsp; &nbsp; if (value.length <= maxSize) {&nbsp; &nbsp; &nbsp; &nbsp; const tempValue = value;&nbsp; &nbsp; &nbsp; &nbsp; const sum = tempValue.reduce((acc, val) => val >= 0 ? acc + val : 0, 0);&nbsp; &nbsp; &nbsp; &nbsp; if (sum <= maxSum && sum > 0) acc.push(value);&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; return acc&nbsp; &nbsp; }, []&nbsp; )}console.log(findArrays(3, 10));