Description
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. The same number may be chosen unlimited times. Return combinations in any order.
Examples
Input:
candidates = [2,3,6,7], target = 7Output:
[[2,2,3],[7]]Explanation:
2+2+3=7 and 7=7 are the only valid combinations.
Input:
candidates = [2,3,5], target = 8Output:
[[2,2,2,2],[2,3,3],[3,5]]Explanation:
Three valid combinations: 2+2+2+2=8, 2+3+3=8, and 3+5=8. Each uses candidates unlimited times.
Input:
candidates = [2], target = 1Output:
[]Explanation:
The smallest candidate (2) is already larger than target (1), so no combination can sum to 1.
Constraints
- •
1 ≤ candidates.length ≤ 30 - •
2 ≤ candidates[i] ≤ 40 - •
All elements of candidates are distinct. - •
1 ≤ target ≤ 40