Given an array of distinct positive integers candidates and a target, return every distinct combination of candidates that sums to target. A candidate may be reused any number of times; two combinations are the same if they use the same values the same number of times. Report each combination in non-descending order, and the combinations sorted lexicographically. No combination works means an empty list.
Examples
Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Example 2:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:
Input: candidates = [2], target = 1
Output: []
Example 4:
Input: candidates = [7,3,2], target = 7
Output: [[2,2,3],[7]]
Explanation: the input order does not matter; the output order is pinned.
Backtracking — choose, recurse, undo. The undo is what makes the rest correct. Pruning: cutting a branch the moment it cannot lead anywhere.
How to think about it
1. DFS That Never Looks Left Optimal
Intuition
Reuse is allowed, so the danger is emitting the same multiset in different orders. Carrying a start index — each level may reuse the current candidate or move right, never left — makes every combination non-descending by construction, which is both the dedup and the required output order. Sorting first also lets the loop stop the moment a candidate exceeds the remainder.
Algorithm
1. Sort the candidates. 2. DFS with a start index and a remaining target. 3. Remaining zero: record the path. 4. Otherwise try each candidate from the start index while it fits, recursing with the SAME index.
Time & Space
Time exponential in the target-to-candidate ratio, which is inherent to enumerating combinations. Space O(target/smallest) for the recursion.