Javascript function to determine if number any combination of numbers in array add up to max value

Question

For example: if arr contains [4, 6, 23, 10, 1, 3] the output should return true because 4 + 6 + 10 + 3 = 23. The array will not be empty, will not contain all the same elements, and may contain negative numbers.
My Attempt
Uses a recursive method to find all permutations of the arr and adds elements up to see if they add up to array max. The function checks all permutations correctly but does not return correct boolean.

function arrayAddition(arr) {
    var arrMax = arr.sort(function(a, b) {
                     return a - b;
                 }).pop();

    function recArrAdd(sub, arr) {

        if (arr.length > 0) {
            var arrSum = sub.concat(arr[0]).reduce(function(prev, curr) {
                return prev + curr;
            });

            if (arrSum === arrMax) return true;
            recArrAdd(sub.concat(arr[0]), arr.slice(1));
            recArrAdd(sub, arr.slice(1));
        }
        return false;
    }

    return recArrAdd([], arr);
}

console.log(arrayAddition([1, 2, 3]));

Can you please check this link.. Similar problem codereview.stackexchange.com/questions/36214/… — Sanket Bajoria
– Sanket Bajoria, Commented Sep 27, 2015 at 13:58
That is a related problem, @SanketBajoria, and I added an answer there. — Pointy
– Pointy, Commented Sep 27, 2015 at 15:09

sokin · Accepted Answer · 2015-09-27 17:21:49Z

I believe that the problem lies in the if (arrSum === arrMax) return true; check. At some points in the execution of the program arrSum is actually equal to the respective arr[0]. But when arr[0] happens to be the MAX element in your array then you get a false positive.

So, you have to incorporate another check : if (arr[0] != arrMax)

Also, your function should not return false when the if (arr.length > 0) check fails. Instead you can use a global flag variable (found as seen in the code below) and return this as the final outcome.

EDIT: Also, the check if (found) return true; is placed right at the top of recArrAdd() for performance reasons: It helps avoid unnecessary further calls, since when found is true the job is done.

For example, without it, recArrAdd() is called 255 times and with it 187 (input [1,3,5,4,25,8,14]).

Here follows your revised code and some sample outputs:

function arrayAddition(arr) {
    var arrMax = Math.max.apply(Math, arr);
    var found = false;


    function recArrAdd(sub, arr) {
        if (found) return true;
        if (arr.length > 0) {
            var arrSum = sub.concat(arr[0]).reduce(function(prev, curr) { return prev + curr;});
            if (arrSum === arrMax){
                if (arr[0] != arrMax){
                    found = true;
                    return found;
                }
            };
            recArrAdd(sub.concat(arr[0]), arr.slice(1));
            recArrAdd(sub, arr.slice(1));
        }
        return found;
    }

    return recArrAdd([], arr);
}

console.log("[1,2,3] -> "+arrayAddition([1,2,3]));
console.log("[1,2,5] -> "+arrayAddition([1,2,5]));
console.log("[1,2,5,4,20,8] -> "+arrayAddition([1,2,5,4,20,8]));
console.log("[1,2,5,4,21,8] -> "+arrayAddition([1,2,5,4,21,8]));
console.log("[1,3,5,4,25,8,14] -> "+arrayAddition([1,3,5,4,25,8,14]));
console.log("[1,3,5,4,45,8,14] -> "+arrayAddition([1,3,5,4,45,8,14]));

which yields:

in Firefox using Firebug.

Jon Koops · Accepted Answer · 2015-09-27 14:18:10Z

0

Are you looking for something like this?:

function sumEqualsMax(values) {
    var maxValue = Math.max.apply(Math, values);
    var sumParts = values.slice();
    sumParts.splice(sumParts.indexOf(maxValue), 1);

    var sumValue = sumParts.reduce(function (previousValue, currentValue) {
        return previousValue + currentValue;
    }, 0);

    return sumValue === maxValue;
}

var values = [4, 6, 23, 10, 3];
console.log(sumEqualsMax(values));

answered Sep 27, 2015 at 14:18

Jon Koops

9,4306 gold badges33 silver badges54 bronze badges

2 Comments

Pointy Over a year ago

It's supposed to return true when some combination of the values (not necessarily all of them) add up to the maximum value.

Jon Koops Over a year ago

Ah, I see. Didn't get that from your question.

sbeliakov · Accepted Answer · 2015-09-27 17:22:41Z

0

If your numbers are bounded by 31 there exists beautiful solution:

Let n be the maximum and arr the rest of numbers. Then the following code checks what you want

var mask = 1;
for (var idx = 0; idx < arr.size; idx++) {
    mask = mask | mask << arr[idx];
}
return (mask >>> n) & 1;

It can be generalized for bigger restrictions using array of boolean instead of bit mask.

Some explanation. At the beginning mask is 00000001, marking that by sums of empty set we can make 0 (as 1 is at position 0). Then on every step mask is mask for all sums we can make. Then by adding arr[idx] for each sum s we can make s + arr[idx]. So mask of new sums will be mask << arr[idx]. But we can still make all old sums of mask mask. So new value for mask is mask | mask << arr[idx]. In the end mask is mask for all possible sums and if n is possible sum then n-th bit ((mask >>> n) & 1) is 1 and 0 in either way.

edited Sep 27, 2015 at 17:22

answered Sep 27, 2015 at 14:08

sbeliakov

2,2092 gold badges21 silver badges37 bronze badges

2 Comments

Daniel Kobe Over a year ago

Can you explain this in more detail? Are these >>> << bitshifters? How does it work?

Pointy Over a year ago

Don't use for ... in for looping through arrays.

Collectives™ on Stack Overflow

Javascript function to determine if number any combination of numbers in array add up to max value

3 Answers 3

Comments

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related