Find all unique combinations of numbers that add up to a target, where each number may be used multiple times.
Given a list of distinct positive integers and a target value, return all unique combinations of the numbers whose sum equals the target.
You may use each candidate any number of times. Two combinations are considered the same if they contain the same values with the same multiplicities, regardless of order.
Return the combinations in any order.
Input Format
- An array of distinct positive integers
candidates - A positive integer
target
Output Format
- Return a list of all unique combinations
- Each combination is a list of integers whose sum is exactly
target
Constraints
1 <= candidates.length- All candidate values are positive and distinct
target > 0- Each candidate can be chosen multiple times
- The number of valid combinations may be large
Example 1
Input
candidates = [2,3,6,7], target = 7
Output
[[2,2,3],[7]]
Explanation
Both [2,2,3] and [7] sum to 7. Order inside a combination does not matter.
Example 2
Input
candidates = [2,3,5], target = 8
Output
[[2,2,2,2],[2,3,3],[3,5]]
Explanation
These are all the unique combinations that add up to 8.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.