Combination Sum
You're given an array of distinct positive integers candidates and a positive integer target. Return every unique combination of candidates whose values add up to target, where each candidate may be used any number of times. Combinations that use the same values the same number of times count once, so [2,2,3] and [3,2,2] are one answer. Return them in any order, or an empty list if there are none.
Examples
candidates = [2,3,6,7], target = 7 returns [[2,2,3],[7]]
2 + 2 + 3 = 7 uses the 2 twice, which is allowed, and 7 on its own is the other answer. Reorderings like [3,2,2] are the same combination, so they don't appear again.
candidates = [2,3,5], target = 8 returns [[2,2,2,2],[2,3,3],[3,5]]
The only ways to make 8 are four 2s, a 2 with two 3s, and 3 + 5. Two 5s would already overshoot to 10.
candidates = [2], target = 1 returns []
The only candidate is 2, which is already bigger than 1, so no combination exists and the result is an empty list.
Constraints
- 1 <= candidates.length <= 30
- 2 <= candidates[i] <= 40
Hints
Order doesn't matter, so each combination should be built in a canonical direction to avoid duplicates, how?
Backtrack while always choosing from index start onward (numbers may repeat).
Recurse with (start, remaining, path). If remaining == 0, snapshot path. For i from start to end, skip candidates[i] if it exceeds remaining (or sort first and break); otherwise push candidates[i], recurse with (i, remaining - candidates[i]), same i so the value can repeat, then pop.
Drill This: Your Approach First
Approach
A recursive helper tracks a start index, the remaining sum and the current path. At each level it tries every candidate from start onward: append it, recurse with the same index i so it can be reused, then pop it. Never going back to earlier indices builds each multiset in one fixed order, so none repeats. When remaining hits 0 the path is saved, and candidates larger than remaining are skipped. With t = target and m = the smallest candidate, paths are at most t/m long.
Time
O(n^(t/m))
Space
O(t/m)
Pitfall
Solutions
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
backtrack(candidates, 0, target, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] cands, int start, int remaining, List<Integer> path, List<List<Integer>> result) {
if (remaining == 0) {
result.add(new ArrayList<>(path));
return;
}
for (int i = start; i < cands.length; i++) {
if (cands[i] > remaining) continue;
path.add(cands[i]);
backtrack(cands, i, remaining - cands[i], path, result);
path.remove(path.size() - 1);
}
}
}class Solution:
def combinationSum(self, candidates, target: int):
result = []
def backtrack(start, remaining, path):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
continue
path.append(candidates[i])
backtrack(i, remaining - candidates[i], path)
path.pop()
backtrack(0, target, [])
return result