122. Combination Sum — Reusable Candidates
Choose candidate values whose sum is exactly the target, allowing each candidate value to be used repeatedly. Different orders of the same chosen values represent the same combination.
Every candidate is positive under this contract. Return each value combination once, including the documented empty combination when the target is zero.
Example 1
Input
nums=[7,2,3,6], target=7
Output
[[2,2,3],[7]]
Explanation: The same 2 may be reused, but [3,2,2] is only a reordering of an existing combination.
Example 2
Input
nums=[], target=0
Output
[[]]
Explanation: The empty combination sums to zero.
Example 3
Input
nums=[4,6], target=5
Output
[]
Explanation: No choice sequence can make the target.
Constraints
0 <= nums.length <= 161 <= nums[i] <= 231 - 10 <= target <= 40- All candidates are distinct and can be reused.
Hints
Hint 1
A combination has one sorted value sequence; use a start frontier to enforce it.
Hint 2
Reusing the current index is safe only if another measure decreases.
Hint 3
Track remaining sum, recurse from i, break on sorted overshoot, and undo after each child.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Repeated choices shrink the remaining sum
[3,2]
6
[[2,2,2],[3,3]]