0

Here's an exercise from the "easy" section of Coderbyte.

Have the function ArrayAdditionI(arr) take the array of numbers and return "true" if any combination of numbers in the array can be added up to equal the largest number in the array, otherwise return "false". For example: if arr contains [4, 6, 23, 10, 1, 3] the output should return true because 4 + 6 + 10 + 3 = 23.

I can imagine an interative solution to this, but the complexity fills me with horror. What do I need to go study to solve this problem?

I'm reading up on the Combination function C(n,k). Is that the right path?

dwilbank
  • 2,470
  • 2
  • 26
  • 37
  • This should help http://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum – elclanrs Aug 21 '13 at 21:40
  • Watching the Stanford lectures. Just wanted to make sure they would definitely apply. Thx. – dwilbank Aug 21 '13 at 21:45

2 Answers2

0

I think it's a 1d bin-packing or a knappsack problem. The problem is also a decision problem so it's a np problem. It can be a weak polynominal problem.

Micromega
  • 12,486
  • 7
  • 35
  • 72
-1

There is perhaps a very naive solution: 

arrAddition = function(values) {
    // sort from largest
    values.sort(function(a, b) {
        return b-a;
    }); 
    var sum = 0;
    // starts from second, and add until reaching the limit
    for (var i = 1; i < values.length; i++) {
        sum += values[i];
        if (sum == values[0]) {
            return true;
        } else if (sum > values[0]) {
            // don't go further
            return false;
        }
    }
    // or fail.
    return false
}

It's even shorter with Underscore handy methods (like reduce).

But I might have totally misunderstood the problem...

Feugy
  • 1,898
  • 14
  • 18
  • yeh I believe that skips certain combinations – dwilbank Aug 21 '13 at 22:03
  • Indeed, it find only one combination ! But that's what you asked for: is there a combination or not. The advantage is that it's really quick: one pass to sort, and another to find the solution. And in optimistic case, you may stop a the third element ! Complexity: O(n) – Feugy Aug 21 '13 at 22:14
  • This will return true if a combination exceeds it as well. It works in the example where all remaining elements add up exactly to the largest element without exceeding it. It would not work for the following: 10, 9, 8. It should return false because 9 + 8 exceeds 10 but will return true. You could change the >= to == but would need to add additional logic to allow for no sequential combinations. E.g. 10, 6, 5, 4. Adding 6 and 5 together would cause it to exceed 10 and fail but that set of numbers should return true (6+4). Good start though. – Kate Aug 21 '13 at 22:21
  • You're perfectly right Simon ! It first time I thought upper or equal. Now it's more complicated :) – Feugy Aug 21 '13 at 22:26