Combination Sum
Combination Sum is LeetCode 39 (Medium). You are given an array of distinct positive integers candidates and a positive target. Return every unique combination of candidates whose numbers add up to target, in any order.
- A candidate may be used any number of times.
- Two combinations are the same if they use the same numbers the same number of times, in any order.
- The inputs are chosen so there are fewer than 150 combinations.
Constraints
- 1 <= candidates.length <= 30
- 2 <= candidates[i] <= 40
- All elements of candidates are distinct.
- 1 <= target <= 40
02
Intuition
Think of the answer as a search tree. The root is the target, each edge subtracts one candidate, and each node records how much is still needed. A node at 0 is a solution; a candidate larger than what remains is a dead end.
Two rules keep the combination sum solution honest. Duplicates like [2, 3] and [3, 2] disappear if a branch only picks candidates at or after the last one chosen, because every combination then has one sorted spelling. Reuse is allowed by letting a branch pick the same candidate again. With sorted input, the first candidate that is too big proves every later one is too, so whole subtrees are skipped.
How to spot this pattern
The question asks for all combinations, not a count or a best value. Listing every solution means exploring choices and undoing them: backtracking. If it only asked for the number of combinations, a DP like Coin Change II would be enough.
03
Approach
Try it first
Before reading on, draw the tree for [2, 3, 6, 7] and target 7 by hand. How do you stop [2, 2, 3] from also appearing as [2, 3, 2]? Where can you stop searching early?
1
Sort the candidates
Sort the candidates first, at O(n log n). Sorting is what makes pruning possible: once candidates[i] > remain, every later candidate is larger too, so the loop can stop instead of testing values that cannot fit.
2
Define the recursive call
Write dfs(start, remain), which tries every candidate from index start onward with remain still to reach, and keep one shared path list for the current choices. Passing start down is what stops a branch from reaching back to earlier candidates and building the same combination in another order.
3
Handle the two ends of a branch
remain == 0: record a copy ofpathand return. The list itself keeps changing as the search backtracks, so storing it directly leaves every saved answer empty.candidates[i] > remain: break; with sorted input nothing from here on can fit.
4
Choose, explore, un-choose
Append c, call dfs(i, remain - c), then pop c. Recursing with the same i rather than i + 1 is what lets a number be used again. Popping restores path, so the next candidate in the loop starts from exactly the state this call received.
04
Combination Sum solution in Python | C++ | Java
▶1class Solution:
▶2 def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
▶3 candidates.sort()
▶4 res, path = [], []
▶5
▶6 def dfs(start: int, remain: int) -> None:
▶7 if remain == 0:
▶8 res.append(path[:])
▶9 return
▶10 for i in range(start, len(candidates)):
▶11 c = candidates[i]
▶12 if c > remain:
▶13 break
▶14 path.append(c)
▶15 dfs(i, remain - c) # i, not i + 1: c may be reused
▶16 path.pop()
▶17
▶18 dfs(0, target)
▶19 return res
▶1class Solution {
▶2public:
▶3 vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
▶4 sort(candidates.begin(), candidates.end());
▶5 vector<vector<int>> res;
▶6 vector<int> path;
▶7 dfs(candidates, 0, target, path, res);
▶8 return res;
▶9 }
▶10
▶11private:
▶12 void dfs(const vector<int>& cands, int start, int remain,
▶13 vector<int>& path, vector<vector<int>>& res) {
▶14 if (remain == 0) {
▶15 res.push_back(path);
▶16 return;
▶17 }
▶18 for (int i = start; i < (int)cands.size(); i++) {
▶19 if (cands[i] > remain) break;
▶20 path.push_back(cands[i]);
▶21 dfs(cands, i, remain - cands[i], path, res); // i: reuse allowed
▶22 path.pop_back();
▶23 }
▶24 }
▶25};
▶1class Solution {
▶2 public List<List<Integer>> combinationSum(int[] candidates, int target) {
▶3 Arrays.sort(candidates);
▶4 List<List<Integer>> res = new ArrayList<>();
▶5 dfs(candidates, 0, target, new ArrayList<>(), res);
▶6 return res;
▶7 }
▶8
▶9 private void dfs(int[] cands, int start, int remain,
▶10 List<Integer> path, List<List<Integer>> res) {
▶11 if (remain == 0) {
▶12 res.add(new ArrayList<>(path));
▶13 return;
▶14 }
▶15 for (int i = start; i < cands.length; i++) {
▶16 if (cands[i] > remain) break;
▶17 path.add(cands[i]);
▶18 dfs(cands, i, remain - cands[i], path, res); // i: reuse allowed
▶19 path.remove(path.size() - 1);
▶20 }
▶21 }
▶22}
candidates[2, 3, 6, 7]sorted, so the loop can stop early
target7root of the search tree
Sort, then search. Each node is the amount still needed. From a node you may add any candidate at or after the one used to reach it, never an earlier one: that rule is what stops
[2,3] and [3,2] from both being produced.path[2]candidates chosen so far
remain5amount still needed
found0combinations so far
Add 2: 7 - 2 = 5 still needed. The recursive call starts at the same index, so 2 may be used again.
path[2, 2]candidates chosen so far
remain3amount still needed
found0combinations so far
Add 2: 5 - 2 = 3 still needed. The recursive call starts at the same index, so 2 may be used again.
path[2, 2, 2]candidates chosen so far
remain1amount still needed
found0combinations so far
Add 2: 3 - 2 = 1 still needed. The recursive call starts at the same index, so 2 may be used again.
path[2, 2, 2, 2]this pick is not kept
remain1cannot fit 2
found0combinations so far
Candidate 2 is bigger than the 1 still needed. Because the list is sorted, every later candidate is bigger too, so the loop breaks here instead of trying them. This cut is why sorting pays off.
path[2, 2, 3]candidates chosen so far
remain0amount still needed
found1combinations so far
Adding 3 leaves exactly 0, so [2, 2, 3] is a valid combination. Record a copy of the path and step back to try the next candidate.
path[2, 2, 6]this pick is not kept
remain3cannot fit 6
found1combinations so far
Candidate 6 is bigger than the 3 still needed. Because the list is sorted, every later candidate is bigger too, so the loop breaks here instead of trying them. This cut is why sorting pays off.
path[2, 3]candidates chosen so far
remain2amount still needed
found1combinations so far
Add 3: 5 - 3 = 2 still needed. The recursive call starts at the same index, so 3 may be used again.
path[2, 3, 3]this pick is not kept
remain2cannot fit 3
found1combinations so far
Candidate 3 is bigger than the 2 still needed. Because the list is sorted, every later candidate is bigger too, so the loop breaks here instead of trying them. This cut is why sorting pays off.
path[2, 6]this pick is not kept
remain5cannot fit 6
found1combinations so far
Candidate 6 is bigger than the 5 still needed. Because the list is sorted, every later candidate is bigger too, so the loop breaks here instead of trying them. This cut is why sorting pays off.
path[3]candidates chosen so far
remain4amount still needed
found1combinations so far
Add 3: 7 - 3 = 4 still needed. The recursive call starts at the same index, so 3 may be used again.
path[3, 3]candidates chosen so far
remain1amount still needed
found1combinations so far
Add 3: 4 - 3 = 1 still needed. The recursive call starts at the same index, so 3 may be used again.
path[3, 3, 3]this pick is not kept
remain1cannot fit 3
found1combinations so far
Candidate 3 is bigger than the 1 still needed. Because the list is sorted, every later candidate is bigger too, so the loop breaks here instead of trying them. This cut is why sorting pays off.
path[3, 6]this pick is not kept
remain4cannot fit 6
found1combinations so far
Candidate 6 is bigger than the 4 still needed. Because the list is sorted, every later candidate is bigger too, so the loop breaks here instead of trying them. This cut is why sorting pays off.
path[6]candidates chosen so far
remain1amount still needed
found1combinations so far
Add 6: 7 - 6 = 1 still needed. The recursive call starts at the same index, so 6 may be used again.
path[6, 6]this pick is not kept
remain1cannot fit 6
found1combinations so far
Candidate 6 is bigger than the 1 still needed. Because the list is sorted, every later candidate is bigger too, so the loop breaks here instead of trying them. This cut is why sorting pays off.
path[7]candidates chosen so far
remain0amount still needed
found2combinations so far
Adding 7 leaves exactly 0, so [7] is a valid combination. Record a copy of the path and step back to try the next candidate.
answer[2,2,3] [7]2 combinations
Done. The green leaves are the 2 combinations. Every other branch ended at a crossed-out pick that was too big, so the search never went below zero.
candidates[2, 3, 5]sorted, so the loop can stop early
target8root of the search tree
Sort, then search. Each node is the amount still needed. From a node you may add any candidate at or after the one used to reach it, never an earlier one: that rule is what stops
[2,3] and [3,2] from both being produced.path[2]candidates chosen so far
remain6amount still needed
found0combinations so far
Add 2: 8 - 2 = 6 still needed. The recursive call starts at the same index, so 2 may be used again.
path[2, 2]candidates chosen so far
remain4amount still needed
found0combinations so far
Add 2: 6 - 2 = 4 still needed. The recursive call starts at the same index, so 2 may be used again.
path[2, 2, 2]candidates chosen so far
remain2amount still needed
found0combinations so far
Add 2: 4 - 2 = 2 still needed. The recursive call starts at the same index, so 2 may be used again.
path[2, 2, 2, 2]candidates chosen so far
remain0amount still needed
found1combinations so far
Adding 2 leaves exactly 0, so [2, 2, 2, 2] is a valid combination. Record a copy of the path and step back to try the next candidate.
path[2, 2, 2, 3]this pick is not kept
remain2cannot fit 3
found1combinations so far
Candidate 3 is bigger than the 2 still needed. Because the list is sorted, every later candidate is bigger too, so the loop breaks here instead of trying them. This cut is why sorting pays off.
path[2, 2, 3]candidates chosen so far
remain1amount still needed
found1combinations so far
Add 3: 4 - 3 = 1 still needed. The recursive call starts at the same index, so 3 may be used again.
path[2, 2, 3, 3]this pick is not kept
remain1cannot fit 3
found1combinations so far
Candidate 3 is bigger than the 1 still needed. Because the list is sorted, every later candidate is bigger too, so the loop breaks here instead of trying them. This cut is why sorting pays off.
path[2, 2, 5]this pick is not kept
remain4cannot fit 5
found1combinations so far
Candidate 5 is bigger than the 4 still needed. Because the list is sorted, every later candidate is bigger too, so the loop breaks here instead of trying them. This cut is why sorting pays off.
path[2, 3]candidates chosen so far
remain3amount still needed
found1combinations so far
Add 3: 6 - 3 = 3 still needed. The recursive call starts at the same index, so 3 may be used again.
path[2, 3, 3]candidates chosen so far
remain0amount still needed
found2combinations so far
Adding 3 leaves exactly 0, so [2, 3, 3] is a valid combination. Record a copy of the path and step back to try the next candidate.
path[2, 3, 5]this pick is not kept
remain3cannot fit 5
found2combinations so far
Candidate 5 is bigger than the 3 still needed. Because the list is sorted, every later candidate is bigger too, so the loop breaks here instead of trying them. This cut is why sorting pays off.
path[2, 5]candidates chosen so far
remain1amount still needed
found2combinations so far
Add 5: 6 - 5 = 1 still needed. The recursive call starts at the same index, so 5 may be used again.
path[2, 5, 5]this pick is not kept
remain1cannot fit 5
found2combinations so far
Candidate 5 is bigger than the 1 still needed. Because the list is sorted, every later candidate is bigger too, so the loop breaks here instead of trying them. This cut is why sorting pays off.
path[3]candidates chosen so far
remain5amount still needed
found2combinations so far
Add 3: 8 - 3 = 5 still needed. The recursive call starts at the same index, so 3 may be used again.
path[3, 3]candidates chosen so far
remain2amount still needed
found2combinations so far
Add 3: 5 - 3 = 2 still needed. The recursive call starts at the same index, so 3 may be used again.
path[3, 3, 3]this pick is not kept
remain2cannot fit 3
found2combinations so far
Candidate 3 is bigger than the 2 still needed. Because the list is sorted, every later candidate is bigger too, so the loop breaks here instead of trying them. This cut is why sorting pays off.
path[3, 5]candidates chosen so far
remain0amount still needed
found3combinations so far
Adding 5 leaves exactly 0, so [3, 5] is a valid combination. Record a copy of the path and step back to try the next candidate.
path[5]candidates chosen so far
remain3amount still needed
found3combinations so far
Add 5: 8 - 5 = 3 still needed. The recursive call starts at the same index, so 5 may be used again.
path[5, 5]this pick is not kept
remain3cannot fit 5
found3combinations so far
Candidate 5 is bigger than the 3 still needed. Because the list is sorted, every later candidate is bigger too, so the loop breaks here instead of trying them. This cut is why sorting pays off.
answer[2,2,2,2] [2,3,3] [3,5]3 combinations
Done. The green leaves are the 3 combinations. Every other branch ended at a crossed-out pick that was too big, so the search never went below zero.
candidates[2]sorted, so the loop can stop early
target1root of the search tree
Sort, then search. Each node is the amount still needed. From a node you may add any candidate at or after the one used to reach it, never an earlier one: that rule is what stops
[2,3] and [3,2] from both being produced.path[2]this pick is not kept
remain1cannot fit 2
found0combinations so far
Candidate 2 is bigger than the 1 still needed. Because the list is sorted, every later candidate is bigger too, so the loop breaks here instead of trying them. This cut is why sorting pays off.
answer[]0 combinations
No combination. Every branch was cut before reaching 0, so the answer is the empty list.
05
Common pitfalls
Restarting the loop at index 0
✗ Wrong
for i in range(len(candidates)):
...
dfs(i, remain - c)✓ Right
for i in range(start, len(candidates)):
...
dfs(i, remain - c)Starting from 0 lets a call go back to smaller candidates, so [2, 2, 3], [2, 3, 2] and [3, 2, 2] are all produced. Starting at start builds each combination in non-decreasing order, exactly once.
Recursing with i + 1
✗ Wrong
dfs(i + 1, remain - c)
✓ Right
dfs(i, remain - c)
i + 1 forbids reusing a number, which is Combination Sum II's rule. For [2, 3, 6, 7] and 7 it would miss [2, 2, 3].
Saving the path without copying it
✗ Wrong
res.append(path)
✓ Right
res.append(path[:])
path is one shared list that keeps changing. Appending it stores a reference, so after the search every saved answer is the same empty list.
06
Complexity
Time
O(n^(T/m + 1))
Space
O(T/m)
T is the target and m the smallest candidate, so T/m is the deepest a path can go and n is the branching. Sorting and the early break cut most branches in practice. Space is the recursion depth, not counting the output.
07
Combination Sum I, II, III and IV
Four problems with nearly the same name. The rules on reuse, duplicates and order decide the technique.
| Problem | Reuse a number? | Input | Output | Technique |
|---|---|---|---|---|
| Combination Sum (39) | yes | distinct numbers | all combinations | backtracking, recurse with i |
| Combination Sum II (40) | no, each once | may contain duplicates | all unique combinations | backtracking with i + 1, skip equal neighbours |
| Combination Sum III (216) | no | digits 1 to 9, exactly k of them | all combinations | backtracking with a size limit |
| Combination Sum IV (377) | yes | distinct numbers | count of ordered sequences | DP, amount in the outer loop |
08
Combination Sum FAQ
What is the combination sum problem?
Given distinct positive numbers and a target, list every combination of those numbers (each usable any number of times) that adds up to the target. For [2, 3, 6, 7] and 7 the answer is [[2, 2, 3], [7]].
How does the combination sum backtracking algorithm work?
- Method: backtracking over a search tree whose nodes are the remaining target.
- Avoid duplicates: each call only uses candidates from its start index onward.
- Allow reuse: recurse with the same index
i. - Base cases: remaining 0, save a copy of the path; candidate larger than remaining, stop the loop (the array is sorted).
- Steps: choose, recurse, un-choose.
- Example:
[2, 3, 6, 7], 7 gives[2, 2, 3]and[7].
Why sort the candidates in combination sum?
After sorting, once one candidate is larger than the remaining amount, every later candidate is too. The loop can break instead of continue, which removes whole subtrees from the search.
How is Combination Sum different from Combination Sum II?
In Combination Sum (39) each number can be used many times and the input has no duplicates, so you recurse with i. In Combination Sum II (40) each number is used at most once and the input can contain duplicates, so you recurse with i + 1 and skip equal numbers at the same level.
Can combination sum be solved with dynamic programming?
Counting the combinations can (that is Coin Change II). Listing them all still needs every combination to be built, so backtracking is the natural fit; a DP that stores lists would use a lot of memory for no gain.