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