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.

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.

• javascript
• algorithm
• subset-sum

• 1 why is 29 not included? – Nina Scholz Commented Dec 19, 2017 at 17:14
• @NinaScholz sorry, my mistake. 29 is included – Usr Commented Dec 19, 2017 at 17:15

4 Answers 4

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

A fast and pact 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./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 plexity low by not using costly array operations. Only a found subset has to be copied to keep track of possible binations. Still, there are probably more clever solutions possible to improve performance.

The method will return the last found bination, 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 binations replace this line:

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

with this:

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

All binations 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]];

Here's a brute force solution. First we get every possible bination of values from the original array, take their sum, and see which of those gets us the highest value without overflowing the given maximum.

var ary = [40, 138, 29, 450];

// Function to construct a power set. A power set is just the set of
// all possible subsets of some given set.
function makePowerSet(ary) {
    powerSet = [];
    for (let ps = 1; ps <= Math.pow(2, ary.length); ps++) {
        subset = [];
        for (let i = 0; i < ary.length; i++) {
            if (ps & Math.pow(2, i)) subset.push(ary[i]);
        }
        powerSet.push(subset);
    }
    return powerSet;
}

// Function to calculate the sum of an array.
function getSum(ary) {
   return ary.reduce((sum, cur) => {
      return sum + cur;
   }, 0);
}

function getSubsetBelow(val, ary) {
    let bestSoFar;
    let bestSoFarSum = 0;
    for (let subset of makePowerSet(ary)) {
        const sum = getSum(subset);
        if (sum > val) continue;
        if (sum > bestSoFarSum) {
            bestSoFar = subset;
            bestSoFarSum = sum;
        }
    }
    
    console.log("Got a best sum value of", bestSoFarSum, "with the subset", bestSoFar);
}

getSubsetBelow(250, ary)

This seems very similar to the knapsack problem, which is NP-hard, so I don't know if you'll ever be able to find an efficient algorithm for this. However, there are definitely a few optimizations that can be made to what I've written here, for example, any element of the array already greater than the limit can't be part of the solution (easy way to eliminate 450).

#Find a maximum sum of a pact subsequence of array elements.

import sys
def solution(A):
 max_ending = max_slice = -sys.maxsize
 if(len(A)==1):
     return A[0]
 else:
     for a in A:
         max_ending =max(a,max_ending + a)
         max_slice = max(max_slice, max_ending)
     return max_slice