Backtracking
LC #39Medium
Combination Sum
Backtracking
AmazonGoogleMetaBloombergProblem
Find all combinations of candidates that sum to target. Numbers can be reused.
arraybacktracking
Constraints
- ›1 ≤ candidates.length ≤ 30
- ›2 ≤ candidates[i] ≤ 40
- ›All candidates are distinct
- ›1 ≤ target ≤ 40
Example
Input
candidates = [2, 3, 6, 7], target = 7Output
[[2,2,3],[7]]Why
2+2+3=7 and 7=7. Numbers may be reused unlimited times