javascript - 返回总和小于或等于n的数组中所有可能的数字组合

var a = [1,3,6,10,-1];
function combinations(array, n) {
}

combinations(a, 9) // should return...
[[1], [3], [6], [-1], [1,3], [1,6], [1,-1], [3,6], [3,-1], [6, -1], [10, -1], [1,3,-1], [3,6,-1], [1,6,-1], [1,3,6,-1]]

也许我错过了一些正确答案，但您明白了。真的很想知道如何解决这个问题!

最佳答案

我要说的问题是，采用数组的幂集，并将其过滤为仅求和大于一定数量的元素。

集合的幂集是该集合的所有子集的集合。 (假设快五倍，您将成为数学家)

例如，[1]的幂集为[[], [1]]，[1, 2]的幂集为[[], [1], [2], [1, 2]]。

首先，我将定义一个powerSet函数，如下所示:

var powerSet = function (arr) {

    // the power set of [] is [[]]
    if(arr.length === 0) {
        return [[]];
    }

    // remove and remember the last element of the array
    var lastElement = arr.pop();

    // take the powerset of the rest of the array
    var restPowerset = powerSet(arr);


    // for each set in the power set of arr minus its last element,
    // include that set in the powerset of arr both with and without
    // the last element of arr
    var powerset = [];
    for(var i = 0; i < restPowerset.length; i++) {

        var set = restPowerset[i];

        // without last element
        powerset.push(set);

        // with last element
        set = set.slice(); // create a new array that's a copy of set
        set.push(lastElement);
        powerset.push(set);
    }

    return powerset;
};

然后，我将定义一个函数，该函数采用数组的幂集，并且仅包括总和小于或等于某个数量的元素:

var subsetsLessThan = function (arr, number) {

    // all subsets of arr
    var powerset = powerSet(arr);

    // subsets summing less than or equal to number
    var subsets = [];

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

        var subset = powerset[i];

        var sum = 0;
        for(var j = 0; j < subset.length; j++) {
            sum += subset[j];
        }

        if(sum <= number) {
            subsets.push(subset);
        }
    }

    return subsets;
};

在大型阵列上，这可能不是很快，但在小型阵列上效果很好。

看起来它为console.log(subsetsLessThan([1,3,6,10,-1], 9));提供了正确的答案

编辑:关于此处设置的功率设置功能的更多信息
[]的唯一子集是[]，因此[]的幂集是仅包含[]的集。那将是[[]]。

如果您传入if，则powerSet函数中的初始[[]]语句立即返回[]。

var powerSet = function (arr) {

    if(arr.length === 0) {
        return [[]];
    }

如果传入至少包含一个元素的集合，则powerSet函数将从删除最后一个元素开始。例如，如果您在powerSet上调用[1, 2]，则变量lastElement将设置为2，而arr将设置为[1]。

    var lastElement = arr.pop();

然后powerSet函数递归调用自身以获取列表“其余”的幂集。如果您已传递[1, 2]，则restPowerset被分配给powerSet([1])，即[[], [1]]。

    var restPowerset = powerSet(arr);

我们定义一个变量，该变量将保留传入的幂的集合，此处为[1, 2]

    var powerset = [];

我们遍历restPowerset中的每个集合。

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

        var set = restPowerset[i];

[1]的任何子集也是[1, 2]的子集，因此我们将其添加到列表中。也就是说，[]和[1]都是[1, 2]的子集。

        powerset.push(set);

如果将元素2添加到[1]的任何子集，它也是[1, 2]的子集，那么我们将其添加到列表中。 [2]和[1, 2]都是[1, 2]的子集。

        set = set.slice(); // copy the array
        set.push(lastElement); // add the element
        powerset.push(set);

就这样。此时，变量powerset是[[], [2], [1], [1, 2]]。把它返还!

    }

    return powerset;
};