39. Combination Sum
You are given an array candidates of distinct positive integers and a positive integer target. Assemble every combination of candidates whose values add up to exactly target — the same candidate may be picked as many times as you like. Two selections count as the same combination when they use each value the same number of times, so order never distinguishes them.
Return the full list in canonical form: inside each combination the numbers appear in non-decreasing order, and the combinations themselves are sorted in ascending lexicographic order. If no combination reaches the target, return an empty list (the raw output prints -1).
Example 1:
Input: candidates = [3, 5, 2], target = 8
Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
Explanation: 8 can be built three ways: four 2s, one 2 with two 3s, or a 3 and a 5. Reuse is allowed, which is why 2 appears up to four times.
Example 2:
Input: candidates = [4, 2, 7], target = 11
Output: [[2, 2, 7], [4, 7]]
Explanation: Only 2 + 2 + 7 and 4 + 7 hit 11. Note [2, 2, 7] precedes [4, 7] lexicographically because 2 < 4.
Constraints:
- 1 ≤ candidates.length ≤ 20
- 2 ≤ candidates[i] ≤ 40, all values distinct
- 1 ≤ target ≤ 40
- Every input yields fewer than 150 combinations.
Hints:
Think of a decision tree: at each step, either commit another copy of the current candidate or move on to a larger one. Sorting the candidates first and never picking a candidate smaller than the last one chosen keeps each combination non-decreasing — permutations simply never get generated.
In the backtracking loop, recurse with the *same* start index j to allow reuse (j + 1 would forbid it), and break out of the loop as soon as a candidate exceeds the remaining sum — everything after it is larger. A DFS over sorted candidates emits the combinations already in lexicographic order, so no final sort is needed.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: candidates = [3, 5, 2], target = 8
Expected output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]