Combination Sum
Medium · Backtracking · Array · Backtracking
Problem
Given distinct positive integers candidates and a target, return every unique combination summing to the target. Each candidate may be used any number of times.
Two combinations differ only if the multiset of numbers differs; order does not matter.
Examples
Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]]
2+2+3 and 7.
Input: candidates = [2], target = 1 Output: []
Unreachable.
Constraints
- 1 <= len(candidates) <= 30
- 2 <= candidates[i] <= 40
- All candidates are distinct
- 1 <= target <= 40
Approaches
- Bottom-up over every target — time O(target · n · combinations), space O(target · combinations)
Related problems
Start free on Cariara · Coding problems · System design studio
