Combination sum
You get a list candidates of different positive integers and a positive integer target. A combination is a group of numbers taken from candidates whose total is exactly target. A group can take the same candidate as many times as you like: with candidates [4, 2, 7] and target 8, [2, 2, 2, 2] counts. Return every combination, as a list of lists.
Two combinations are the same when they use the same numbers the same number of times, in any order: [2, 2, 4] and [4, 2, 2] are one combination, so it appears once. Return the combinations in any order, and the numbers inside each in any order. If no combination works, return an empty list.
candidates = [4, 2, 7], target = 8Output[[2, 2, 2, 2], [2, 2, 4], [4, 4]]The 7 never fits: alone it is 1 short, and adding even a 2 goes over.
candidates = [5, 3], target = 11Output[[3, 3, 5]]3 + 3 + 5 = 11 is the only way. Only 3s give 9 or 12, never 11, and two 5s leave 1, which nothing fills.
candidates = [4, 6], target = 9Output[]Sums of 4s and 6s are always even, so 9 is out of reach.
1 ≤ len(candidates) ≤ 30
2 ≤ candidates[i] ≤ 40, and all candidates are different.
1 ≤ target ≤ 50
The answer has at most 500 combinations.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.