返回总和小于或等于n的数组中所有可能的数字组合 [英] Return all possible combinations of numbers in an array whose sum is less than or equal to 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]]

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

maybe i'm missing some correct answers but you get the idea. Really dying to know how to solve this!

推荐答案

我会说这里的问题是获取数组的幂集，并将其过滤为仅包含总和大于一定数的元素.

I would say the problem here is to take the power set of an array, and filter it down to only the elements whose sum is greater than a certain number.

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

The power set of a set is the set of all subsets of that set. (Say that five times fast and you'll be a mathematician)

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

For example, the power set of [1] is [[], [1]] and the power set of [1, 2] is [[], [1], [2], [1, 2]].

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

First I would define a powerSet function like this:

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

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

Then I would define a function that takes the power set of the array and only includes elements whose sum is less than or equal to some amount:

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

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

This might not be fast on large arrays, but it works well for small ones.

它似乎为console.log(subsetsLessThan([1,3,6,10,-1], 9));

此处介绍了有关功率设置功能的更多信息

[]的唯一子集是[]，因此[]的幂集是仅包含[]的集.就是[[]].

The only subset of [] is [], so the power set of [] is a set containing only []. That would be [[]].

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

The initial if statement in the powerSet function immediately returns [[]] if you pass in [].

var powerSet = function (arr) {

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

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

If you pass in a set with at least one element, the powerSet function begins by removing the last element. For example, if you call powerSet on [1, 2], the variable lastElement will be set to 2 and arr will be set to [1].

    var lastElement = arr.pop();

然后，powerSet函数递归调用自身以获取列表其余"的幂集.如果您已通过[1, 2]，则将restPowerset分配给powerSet([1])，即[[], [1]].

Then the powerSet function recursively calls itself to get the power set of the "rest" of the list. If you had passed in [1, 2], then restPowerset is assigned to powerSet([1]) which is [[], [1]].

    var restPowerset = powerSet(arr);

我们定义了一个变量，该变量将保留传入的幂集，这里是[1, 2]

We define a variable that's going to hold the power set of what was passed in, here [1, 2]

    var powerset = [];

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

We loop through every set in restPowerset.

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

        var set = restPowerset[i];

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

Any subset of [1] is also a subset of [1, 2] so we add it to the list. That is, [] and [1] are both subsets of [1, 2].

        powerset.push(set);

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

If you add the element 2 to any subset of [1], that is also a subset of [1, 2], so we add it to the list. Both [2] and [1, 2] are subsets of [1, 2].

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

仅此而已.此时，变量powerset是[[], [2], [1], [1, 2]].退货！

That's all. At this point, the variable powerset is [[], [2], [1], [1, 2]]. Return it!

    }

    return powerset;
};

这篇关于返回总和小于或等于n的数组中所有可能的数字组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！