Get the sum of array items that are equal to the target (Subset sum)

Question

I need to get the sum of array items that are equal to the target. If the sum of array item will not equal to the target I would like to get the highest sum that is less than the target.

Here is an example:

Input: [4, 6, 8, 12, 4, 6, 6, 12, 4, 4,4]

Results: [12] [12] [8, 4] [6, 6] [4,4,4] [6,4]

Note: The array item can only be used once.

Currently here is what I have right now:

    var subset_sum = function (items, target) {
    var results = [];

    items.sort(function (a, b) { return b - a });

    ss = function (items) {
        var item = items.shift();
        if (item < target) {
            var perms = [];
            perms.push(item);
            var isItemPush = false;

            var counter = 0
            var innerSubset = function () {
                if (item + items[counter] === target) {
                    perms.push(items[counter])
                    items.splice(counter, 1);
                    results.push(perms);
                    isItemPush = true;
                } else {
                    if (counter < items.length) {
                        counter += 1;
                        innerSubset();
                    }
                }
            }

            innerSubset();

        } else {
            results.push(item);
        }

        if (items.length === 0) {
            return results;
        }

        return ss(items);
    }
    return ss(items)
}

window.onload = function () {
    var items = [4, 6, 8, 12, 4, 6, 6, 12, 4, 4];
    target = 12;

    result = subset_sum(items, target);
    console.log(result);
}

The problem with this approach is that it is only one or two dimensional. From the example above, it does not return the result [4,4,4] and 6.

is the target 12 in your example? I dont really get how your input yields those results. Can you show step by step example? — Sionnach733, May 02 '14 at 10:29
yes The target is 12 in my example. For example: if my current item is 4 I will loop the other items in the array and look for a number that once add to the current item the result will equal to 12 which is the target. Please let me know if you need more example. — Pinoy2015, May 02 '14 at 10:43
But how can the result include both [8, 4] and [4,4,4] when there's only 3 instances of the number 4 in the original array? — Strille, May 02 '14 at 11:29
What's the aim? As many groups of exact matches as possible? — Ja͢ck, May 02 '14 at 11:42

score 10 · Accepted Answer · answered May 02 '14 at 11:36

Very similar solution to yours, a bit unclear if it's helpful:

numbers = [4, 6, 8, 12, 4, 6, 6, 12, 4, 4];

var result = createSubsets(numbers, 12);

console.log('Result', JSON.stringify(result));

function createSubsets(numbers, target) {
    // filter out all items larger than target
    numbers = numbers.filter(function (value) {
        return value <= target;
    });

    // sort from largest to smallest
    numbers.sort(function (a, b) {
        return b - a;
    });

    // array with all the subsets
    var result = [];

    while (numbers.length > 0) {
        var i;
        var sum = 0;
        var addedIndices = [];

        // go from the largest to the smallest number and
        // add as many of them as long as the sum isn't above target
        for (i = 0; i < numbers.length; i++) {
            if (sum + numbers[i] <= target) {
                sum += numbers[i];
                addedIndices.push(i);
            }
        }

        // remove the items we summed up from the numbers array, and store the items to result
        // since we're going to splice the numbers array several times we start with the largest index
        // and go to the smallest to not affect index position with splice.
        var subset = [];
        for (i = addedIndices.length - 1; i >= 0; i--) {
            subset.unshift(numbers[addedIndices[i]]);
            numbers.splice(addedIndices[i], 1);
        }
        result.push(subset);
    }

    return result;
}

Produces array:

[12],[12],[8,4],[6,6],[6,4],[4,4]

There's no limit regarding the subset length. If you add one more 4 to the numbers array you will get result:

[12],[12],[8,4],[6,6],[6,4],[4,4,4]

JSFiddle: http://jsfiddle.net/kUELD/

The first result is not optimized ... not exactly clear from the question but I'd reckon a group of three 4's and one 6 should be preferred over a group of 10 and 8. — Ja͢ck, May 02 '14 at 11:46
There are more efficient ways to do this. The filter has to check each element once, or O(n). Then the sort will probably take O(n log(n)) time. For better alternatives with dynamic programming, see https://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum — TomDane, Aug 30 '18 at 11:28

Get the sum of array items that are equal to the target (Subset sum)

1 Answers1

Linked