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

Question

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]]

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

Answer 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;
};

Answer 2

蛮力 O(N*2 ^N ) 解决方案，其中N = a.length < 31。

这使用索引i作为位字段，filter将a每次迭代中的元素转换为子列表。

var a = [1,3,6,10,-1];

function combinations(array, n) {
    var lists = [], M = 1<<array.length;
    for( var i = 1 ; i < M ; ++i ) {
        var sublist = array.filter(function(c,k){return i>>k & 1});
        if( sublist.reduce(function(p,c){return p+c},0) <= n )
            lists.push(sublist);
    }
    return lists;
}

console.log(JSON.stringify(combinations(a,9)));

[[1],[3],[1,3],[6],[1,6],[3,6],[-1],[1,-1],[3,-1], [1,3,-1],[6,-1],[1,6,-1],[3,6,-1],[1,3,6,-1],[10,-1 ]]