Combination Sum
Part of Practice: The Big Three
Given an array of distinct positive integers candidates and a target integer, return every unique combination of candidates that sums exactly to the target. The same candidate may be used any number of times within a combination. Two combinations are the same if they use the same multiset of numbers, regardless of order — so [2, 2, 3] and [2, 3, 2] count once.
There are at most 30 candidates, each between 2 and 40, and the target is at most 40; the number of valid combinations is guaranteed to be small (under 150).
Examples
- Input:
- candidates = [2, 3, 6, 7], target = 7
- Output:
- [[2, 2, 3], [7]]
2 + 2 + 3 = 7 (2 reused twice) and 7 alone. Nothing else reaches exactly 7.
- Input:
- candidates = [2, 3, 5], target = 8
- Output:
- [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
Three distinct multisets sum to 8, each using repetition where needed.
- Input:
- candidates = [2], target = 1
- Output:
- []
The only candidate exceeds the target, so no combination exists.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.