javascript - find subset that gives maximum sum under a certain limit (subset sum )

Question

I have an array with some integer values, and I need to get a subset of them that gives me the maximum sum that is inferior to a given value.
So let's say I have this array:

[40, 138, 29, 450]

I would like to get a subset of this array that maximize the sum but is inferior to a limit given by the user, let's say 250. In this case it should return [139, 40, 29].
I had a look at this question and related answer, and tried to use the code given, but I didn't understand it very well. Anyway I've tried it, setting the min to 0 and the max to the limit given, but it keeps returning me "5" that is not correct, since the limit is like 300 and the numbers in my array are all over 50.
I couldn't find anything that could help me, so I'm asking if anyone could give me some code or pseudocode to understand how to do this.

Answer 1

Basically you could either add the element at the index to a temporary array or not. Then check if the index reaches the lenght of the array or if the sum is greater than the wanted sum, then either check the sum and add the temp array to the result set, or not.

Proceed until all indices are visited.

function getCombinations(array, sum) {
    function add(a, b) { return a + b; }

    function fork(i, t) {
        var r = (result[0] || []).reduce(add, 0),
            s = t.reduce(add, 0);
        if (i === array.length || s > sum) {
            if (s <= sum && t.length && r <= s) {
                if (r < s) {
                    result = [];
                }
                result.push(t);
            }
            return;
        }
        fork(i + 1, t.concat([array[i]]));
        fork(i + 1, t);
    }

    var result = [];
    fork(0, []);
    return result;
}

console.log(getCombinations([40, 138, 29, 450], 250));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

A fast and compact solution:

function maxSum(input, limit) {
    const sums = {};
    let max = 0;

    const collectSums = (n, i, values) => {
        for (; i < input.length; i++) {
            const sum = n + input[i];
            if (sum <= limit) {
                values.push(input[i]);
                if (sum >= max && values.length > 1) {
                    max = sum;
                    sums[max] = values.slice(); // https://jsperf.com/copying-an-array
                }
                collectSums(sum, i + 1, values);
            }
        }
        values.pop();
    };

    collectSums(0, 0, []);

    return sums[max] || [];
}

Apart from the necessary iterations of the input this solution tries to keep complexity low by not using costly array operations. Only a found subset has to be copied to keep track of possible combinations. Still, there are probably more clever solutions possible to improve performance.

The method will return the last found combination, this means that two input lists with the same values in different order might yield different results:

maxSum([1, 4, 200, 5], 205) == [200, 5];
maxSum([5, 200, 1, 4], 205) == [200, 1, 4];

If you want all possible combinations replace this line:

sums[max] = values.slice(); // https://jsperf.com/copying-an-array

with this:

sums[max] = sums[max] || [];
sums[max].push(values.slice());

All combinations are then returned:

maxSum([1, 4, 200, 5], 205) == [[1, 4, 200], [200, 5]];

But note that this will always return an array of arrays, even when there is only one possibility:

maxSum([40, 138, 29, 450], 250) == [[40, 138, 29]];