Let's take another example. If the input was [3, 2, 5, 1]
and our target number was 6
, we'd witness the following if we did tried the brute force solution by hand:
xxxxxxxxxx
// the left side are the subsets we're trying
​
3 & 2 // curr_sum is 5, < 6, continue
3 & 2 & 5 // too big, skip
2 & 5 // curr_sum is 7, skip
5 & 1 // match!
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment