LeetCode problem #39: Combination Sum (JavaScript)
In this LeetCode problem, we’re given an array of numbers, and a target. Our job is to come up with every possible unique way to make that target by adding the numbers in the array. We can use the numbers multiple times, and the arrangement is considered unique if the quantity of at least one number is different.
For example, given the array of numbers [2, 5, 6] and a target of 12, the solutions include [2, 2, 2, 2, 2, 2], [2, 2, 2, 6] , [2, 5, 5] and [6, 6,]. [6, 2, 2, 2] is not an option because it is simply a rearrangement of the 2nd solution and thus is not unique.
Solution: Backtracking
The main solution here is not all that far from the brute-force option. We start at the first number, and we keep adding it until we hit the target, like so:
[2] — not enough (2)[2, 2] — not enough (4)[2, 2, 2] — not enough (6)[2, 2, 2, 2] — not enough (8)[2, 2, 2, 2, 2] — not enough (10)[2, 2, 2, 2, 2, 2] — bingo! (12)
Now that we have a correct combination, we can swap out the last number for each of the remaining options, like so:
[2, 2, 2, 2, 2, 5] — too much(15)[2, 2, 2, 2, 2, 6] — too much(16)
Now that we’ve exhausted that, we remove that last number and try all combinations of the previous number:
[2, 2, 2, 2, 5] — too much(13)[2, 2, 2, 2, 6] — too much(14)
We repeat this process until we have exhausted all possibilities starting with 2, and then we move onto the next number, following the same process.
Now, one thing you may have noticed is that even when we’ve found a combination that is greater than or equal to the solution, we continue to try other numbers, even if they’re bigger (and are thus impossible combinations). We can solve this problem by first sorting the array, which then allows us to break from the current batch once we have met or exceeded the target. Once we have done that, our complete flow looks like this:
[ 2 ]
[ 2, 2 ]
[ 2, 2, 2 ]
[ 2, 2, 2, 2 ]
[ 2, 2, 2, 2, 2 ]
[ 2, 2, 2, 2, 2, 2 ] — success!
[ 2, 2, 2, 5 ]
[ 2, 2, 2, 6 ] — success!
[ 2, 2, 5 ]
[ 2, 2, 6 ]
[ 2, 5 ]
[ 2, 5, 5 ] — success!
[ 2, 6 ]
[ 5 ]
[ 5, 5 ]
[ 5, 6 ]
[ 6 ]
[ 6, 6 ] — success!
As you can see, we have tried 18 different combinations, significantly less than the 27 possible combinations from the 3 provided numbers, and we have been able to do so by exiting early on some combinations, thanks to our pre-sorting.
Now that the theory’s out of the way, here’s the code:
Not great on readability (backtracking rarely is), but incredibly simple, huh?