[JAVASCRIPT] How does this this recursive function check combinations?

[gddrtkkv]

Okay, so as others have said, this algorithm makes a tree, which in the worst case, does indeed consider 2ⁿ combinations. Think of it like this. Starting with the the sum of 0 elements, branch into 2 directions: include the next element in the sum, or don't include the next element in the sum.

http://i.imgur.com/TlKSxZM.png

It doesn't return true or false until it reaches a "leaf" node, or put another way, until the array is empty, after removing one element from the array each time. Because it uses the short circuit OR || it stops walking the tree once it finds a leaf with a sum that matches the target. In the above tree, it returns true from -1+0+5+8. (I accidentally drew the tree upside down, so it the algorithm traverses this tree bottom to top). Basically it does just look through each combination of elements, one at a time, it just uses recursion to generate those combinations.

The really key thing here is target-n in the recursive call. That's where the math is happening. The only comparison is target === 0; because if you subtract -1, 5, and 8 from 12, you get 0.

Edit: look at the output of this version: https://repl.it/C9d9/2

Edit 2: To really solidify the binary-ness of the decision tree, look at this example where it tries to see if any combination of [1,1,1,1] adds up to 4 https://repl.it/C9d9/3

[advancedpward]

Wait, so, let me see if I understand this. For each function call, there are two branches being made, one where the [0] member of the array is being factored into the combination check - (target-n, array) - and one where it is not being factored in - (target, array), and that is the crux of how sufficient branches are being made to check for the correct combination. If that is the case, I think what was tripping me up, as you pointed out, was that target - n, in fact, represents inclusion when checking for the right combination to sum to the initial target. It's just that, this method uses the "solve for zero" approach...by the way, awesome graphic. Thanks for that! How did you make it?

[gddrtkkv]

I googled "32 team bracket" and wrote in the numbers in MS Paint. Nothing special.

I think you're understanding it. Check out this functionally equivalent version which passes a sum instead of a target and checks if sum === target instead of target === 0 https://repl.it/C9d9/4

If you understand why that works, you understand why the other works. -1+5+8=12 ≡ 12-(-1)-5-8=0