All Unique Combinations That Sum Up to Target Number
Given a list of distinct positive integers candidates and a positive integer target, return every unique combination whose values add up to target.
Each candidate may be selected any number of times. Represent each combination as a comma-separated string containing its values in nondecreasing order.
Method Signature
List<String> combinationSum(List<Integer> candidates, int target)
candidates contains the distinct positive integers that may be selected.target is the required sum of each returned combination.- Return each combination as a comma-separated string, such as
"2,2,3".
- Sort the values within each combination in nondecreasing order.
- Sort the combinations lexicographically by their integer values before converting them to strings.
- Return an empty list when no valid combination exists.
Constraints
1 <= candidates.size() <= 301 <= candidates.get(i) <= 401 <= target <= 40- Every value in
candidates is distinct.
- All candidate values and
target are positive integers.
- The returned list contains no duplicate combinations.
Examples
Example 1
combinationSum(candidates = [2, 4, 5], target = 8)
Output: ["2,2,2,2", "2,2,4", "4,4"]
Each returned combination sums to 8, and a candidate may be used repeatedly.
Example 2
combinationSum(candidates = [3, 6, 8], target = 12)
Output: ["3,3,3,3", "3,3,6", "6,6"]
Example 3
combinationSum(candidates = [4, 7, 10], target = 5)
Output: []
No combination of the available candidates adds up to 5.