Adding up all combinations of number in an array

arrays, javascript

Solution

More concretely, you're looking for a particular sum of each set in the power set of your collection of numbers.

You can accomplish this with the following bit of code.

function powerset(arr) {
    var ps = [[]];
    for (var i=0; i < arr.length; i++) {
        for (var j = 0, len = ps.length; j < len; j++) {
            ps.push(ps[j].concat(arr[i]));
        }
    }
    return ps;
}

function sum(arr) {
    var total = 0;
    for (var i = 0; i < arr.length; i++)
        total += arr[i];
    return total
}

function findSum(numbers, targetSum) {
    var numberSets = powerset(numbers);
    for (var i=0; i < numberSets.length; i++) {
        var numberSet = numberSets[i]; 
        if (sum(numberSet) == targetSum)
            return numberSet;
    }
}

Example invocation:

>> findSum([1,2,3,4,5],6)
[1, 2, 3]
>> findSum([1,2,3,4,5],0)
[]
>> findSum([1,2,3,4,5],11)
[1, 2, 3, 5]

If you'd like to collect all of the subsets whose sum is the value (rather than the first one, as implemented above) you can use the following method.

function findSums(numbers, targetSum) {
    var sumSets = [];
    var numberSets = powerset(numbers);
    for (var i=0; i < numberSets.length; i++) {
        var numberSet = numberSets[i]; 
        if (sum(numberSet) == targetSum)
            sumSets.push(numberSet);
    }
    return sumSets;
}

Example invocation:

>> findSums([1,2,3,4,5],5);
[[2,3],[1,4],[5]]
>> findSums([1,2,3,4,5],0);
[[]]

Problem

I am trying to write a program in javascript that gets an unspecified number of numbers out of a html textarea and tries all combinations (adding all numbers with eachother) to see if it mathches a number you specified. Now I can make an array out of the string in the textarea and using `for` loops I add these up (see below code). The problem how can you do this for an unspecified number of numbers that are to be added up (e.g. adding up 7 different number if you enter 7 numbers in textarea)? I was thinking of using a second array and, which gets the numbers to add up out of the first loop. And then make te lenght of the loop variable by using a for loop with the lenght of the array containing all numbers (lines in my example) as endvalue. How can I fill in the values of this 2nd array, making sure all combinations are used? By the way, I wanted this code because I am a auditor. Sometimes a client reverses a couple of amounts in one booking, without any comment. This code will make it a lot easier to check what bookings have been reversed edit: The awnser of cheeken seems to be working I only have one remark. What if multiple sub sets of your power set added up result in the number you are looking for? e.g.:findSum([1,2,3,4,5],6) can result [1,2,3] but also [2,4] or [1,5]. is it possible to let the function return multiple sub sets? Found the answer my self :) I replaced code ``` return numberSet; ``` By ``` document.getElementById("outp").value=document.getElementById("outp").value+ numberSet +"\n"; ``` Thank you very much Cheeken One more additional question. How do i format the input for parsing that function? The code below doesn't seem to work. inp is the ID of the textarea where the input is (the numbers are seperated with a semicolumn. The variable ge works so there is no problem there (tested it with [1,2,3,4] and it worked. What is wrong with this code? re edit: found the solution. The array needed to be parsed as a floating number added this code.` ``` for (var i=0; i < lines.length; i++) { lines[i]= parseFloat(lines[i]); } findSum(document.getElementById("inp").value.split(";"), ge); ``` Code: ``` <!DOCTYPE html> <html> <head> <script type="text/javascript"> function powerset(arr) { var ps = [[]]; for (var i=0; i < arr.length; i++) { for (var j = 0, len = ps.length; j < len; j++) { ps.push(ps[j].concat(arr[i])); } } return ps; } function sum(arr) { var total = 0; for (var i = 0; i < arr.length; i++) total += arr[i]; return total } function findSum(numbers, targetSum) { var numberSets = powerset(numbers); for (var i=0; i < numberSets.length; i++) { var numberSet = numberSets[i]; if (sum(numberSet) == targetSum) document.getElementById("outp").value=document.getElementById("outp").value+ numberSet +"\n"; } } function main() { ge= document.getElementById("getal").value; findSum([1,1,0.5,0.1,0.2,0.2], ge); } </script> </head> <body> <input type="button" onclick="main()" value="tel" /><input type="text" id="getal" /><br> input<br><textarea id="inp" ></textarea><br> output<br><textarea id="outp" ></textarea><br> document.getElementById("inp").value.split(";") </body> </html> ```

Original source