Combination Sum
Problem
Given an array of distinct integers candidates and an integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order. The same number may be chosen from candidates an unlimited number of times.
- 1 ≤ candidates.length ≤ 30
- 2 ≤ candidates[i] ≤ 40
- 1 ≤ target ≤ 40
Example
candidates = [2,3,6,7], target = 7[[2,2,3],[7]]Starting with an empty path and total 0, the algorithm explores including 2 repeatedly: [2], total=2; then [2,2], total=4; then [2,2,3], total=7, which matches the target and is added to results. It backtracks by removing the last 3 and tries other candidates. Another path is choosing 7 directly, which also sums to 7. The recursion systematically explores all combinations by choosing or skipping candidates, ensuring no duplicates and covering all valid sums.
Approach
Straightforward Solution
A brute-force method would generate all possible combinations of all lengths and check sums, which is combinatorially explosive and inefficient.
Core Observation
The problem requires enumerating all unique combinations summing to a target, with unlimited reuse of elements. This naturally forms a decision tree where each candidate can be chosen multiple times or skipped, making backtracking the ideal approach.
Path to Optimal
The key insight is to structure the search as a depth-first traversal of a decision tree, where at each step the algorithm decides to include the current candidate (and recurse with the same index) or skip it (recurse with the next index). This avoids duplicates by always moving forward in the candidate list and allows unlimited reuse by not advancing the index when including a candidate.
Optimal Approach
Use a recursive DFS function with parameters: current index, current path, and current total sum. When total equals target, add a copy of the path to results. If total exceeds target or index is out of bounds, backtrack. The recursion explores two branches at each step: include the candidate and recurse with the same index, or skip it and recurse with the next index. This ensures all valid combinations are found efficiently.
Time
O(2^t)
The time complexity is exponential in the target value t, as the recursion explores all possible combinations of candidates that sum up to target, which can be exponential in the worst case.
Space
O(t)
The recursion stack and current path can grow up to length t in the worst case (e.g., repeatedly choosing the smallest candidate), so auxiliary space is O(t). The output space is not counted here.
Pattern Spotlight
Backtracking (State Restoration)
For 'find all combinations/permutations' problems, use a 'choose, explore, un-choose' backtracking template. The critical step is to 'un-choose' (e.g., path.pop()) after the recursive call returns, which cleans up the state for the next branch of the search.
Solution
| 1 | class Solution:
|
| 2 | def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
|
| 3 | res = []
|
| 4 |
|
| 5 | def dfs(i, cur, total):
|
| 6 | if total == target:
|
| 7 | res.append(cur.copy())
|
| 8 | return
|
| 9 | if i >= len(candidates) or total > target:
|
| 10 | return
|
| 11 |
|
| 12 | cur.append(candidates[i])
|
| 13 | dfs(i, cur, total + candidates[i])
|
| 14 |
|
| 15 | cur.pop()
|
| 16 | dfs(i + 1, cur, total)
|
| 17 |
|
| 18 | dfs(0, [], 0)
|
| 19 | return res |
| 1 | import java.util.ArrayList; |
| 2 | import java.util.List; |
| 3 | |
| 4 | class Solution { |
| 5 | public List<List<Integer>> combinationSum(int[] candidates, int target) { |
| 6 | List<List<Integer>> res = new ArrayList<>(); |
| 7 | dfs(candidates, target, 0, new ArrayList<>(), 0, res); |
| 8 | return res; |
| 9 | } |
| 10 | |
| 11 | private void dfs(int[] candidates, int target, int i, List<Integer> cur, int total, List<List<Integer>> res) { |
| 12 | if (total == target) { |
| 13 | res.add(new ArrayList<>(cur)); |
| 14 | return; |
| 15 | } |
| 16 | if (i >= candidates.length || total > target) { |
| 17 | return; |
| 18 | } |
| 19 | |
| 20 | cur.add(candidates[i]); |
| 21 | dfs(candidates, target, i, cur, total + candidates[i], res); |
| 22 | cur.remove(cur.size() - 1); |
| 23 | dfs(candidates, target, i + 1, cur, total, res); |
| 24 | } |
| 25 | } |
| 1 | #include <vector> |
| 2 | |
| 3 | using namespace std; |
| 4 | |
| 5 | class Solution { |
| 6 | public: |
| 7 | vector<vector<int>> combinationSum(vector<int>& candidates, int target) { |
| 8 | vector<vector<int>> res; |
| 9 | vector<int> cur; |
| 10 | dfs(candidates, target, 0, cur, 0, res); |
| 11 | return res; |
| 12 | } |
| 13 | |
| 14 | private: |
| 15 | void dfs(const vector<int>& candidates, int target, int i, vector<int>& cur, int total, vector<vector<int>>& res) { |
| 16 | if (total == target) { |
| 17 | res.push_back(cur); |
| 18 | return; |
| 19 | } |
| 20 | if (i >= (int)candidates.size() || total > target) { |
| 21 | return; |
| 22 | } |
| 23 | |
| 24 | cur.push_back(candidates[i]); |
| 25 | dfs(candidates, target, i, cur, total + candidates[i], res); |
| 26 | cur.pop_back(); |
| 27 | dfs(candidates, target, i + 1, cur, total, res); |
| 28 | } |
| 29 | }; |
| 1 | var combinationSum = function(candidates, target) { |
| 2 | const res = []; |
| 3 | |
| 4 | function dfs(i, cur, total) { |
| 5 | if (total === target) { |
| 6 | res.push(cur.slice()); |
| 7 | return; |
| 8 | } |
| 9 | if (i >= candidates.length || total > target) { |
| 10 | return; |
| 11 | } |
| 12 | |
| 13 | cur.push(candidates[i]); |
| 14 | dfs(i, cur, total + candidates[i]); |
| 15 | cur.pop(); |
| 16 | dfs(i + 1, cur, total); |
| 17 | } |
| 18 | |
| 19 | dfs(0, [], 0); |
| 20 | return res; |
| 21 | }; |
Step-by-Step Solution
Initialize Result Container and Start Recursive Search
| 3 | res = []
|
| 18 | dfs(0, [], 0)
|
| 19 | return res |
Objective
To prepare the container for storing valid combinations and initiate the recursive backtracking process from the first candidate.
Key Insight
The result list accumulates all valid combinations found during recursion. Starting the DFS from index 0 with an empty path and total 0 represents the root of the decision tree, from which all combinations are explored systematically.
Interview Quick-Check
Core Logic
The recursion starts at index 0 with an empty path and total 0, representing the initial state before any candidates are chosen.
State & Boundaries
The result list must be initialized before recursion to collect all valid combinations.
Define DFS Helper and Terminate Upon Reaching Target or Invalid State
| 5 | def dfs(i, cur, total):
|
| 6 | if total == target:
|
| 7 | res.append(cur.copy())
|
| 8 | return
|
| 9 | if i >= len(candidates) or total > target:
|
| 10 | return
|
Objective
To define the base cases that stop recursion when a valid combination is found or when the current path cannot lead to a valid solution.
Key Insight
When the total sum equals the target, the current path is a valid combination and must be copied and added to results. If the index exceeds the candidate list or the total exceeds the target, no valid combination can be formed from this path, so recursion stops. These base cases prune the search space and prevent unnecessary exploration.
Interview Quick-Check
State & Boundaries
Check if total == target to add a valid combination, and if index is out of bounds or total > target to prune invalid paths.
Common Pitfalls & Bugs
Forgetting to copy the current path when adding to results leads to incorrect answers due to shared mutable state.
Explore Including Current Candidate and Backtrack
| 12 | cur.append(candidates[i])
|
| 13 | dfs(i, cur, total + candidates[i])
|
| 15 | cur.pop()
|
Objective
To explore the decision branch where the current candidate is included, updating the path and total accordingly.
Key Insight
Including the current candidate means adding it to the path and increasing the total sum. The recursive call with the same index allows unlimited reuse of this candidate. After recursion returns, the candidate is removed (un-chosen) to restore state for exploring other branches. This 'choose, explore, un-choose' pattern is fundamental to backtracking.
Interview Quick-Check
Core Logic
Including the candidate and recursing with the same index enables repeated use of the candidate in combinations.
State & Boundaries
The pop operation after recursion restores the path state for the next exploration branch.
Common Pitfalls & Bugs
Omitting the pop leads to incorrect paths accumulating candidates from multiple branches.
Explore Skipping Current Candidate to Move Forward
| 16 | dfs(i + 1, cur, total)
|
Objective
To explore the decision branch where the current candidate is skipped, advancing the index to consider the next candidate.
Key Insight
Skipping the current candidate means moving forward in the candidate list without changing the current path or total. This ensures all candidates are considered and prevents duplicates by always moving forward. This branch complements the inclusion branch, together covering all possible combinations.
Interview Quick-Check
Core Logic
Skipping the candidate and recursing with the next index ensures exploration of all candidate subsets without duplication.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
cur.pop()Remove the last candidate from the path to backtrack.
This 'un-choose' step restores the path state, enabling exploration of alternative branches without contamination from previous choices.
res.append(cur.copy())Add a copy of the current path to the results.
Copying the path is essential because the path list is mutable and will be modified during backtracking; without copying, all results would reference the same list.
dfs(i, cur, total + candidates[i])Recursively explore further combinations including the current candidate.
Recursing with the same index allows unlimited reuse of the candidate, essential for covering all valid combinations.
if total == target:Check if the current total equals the target sum.
This base case identifies when a valid combination has been found and triggers adding it to the results.
if i >= len(candidates) or total > target:Check if the index is out of bounds or total exceeds target.
This base case prunes invalid paths early, preventing unnecessary recursion and improving efficiency.
dfs(i + 1, cur, total)Recursively explore combinations skipping the current candidate.
Advancing the index without changing the path or total explores the alternative branch, ensuring all candidates are considered and duplicates avoided.
def dfs(i, cur, total):Define the DFS helper for exploring candidate combinations.
The helper carries the candidate index, current combination, and running total, which are the full state needed for the backtracking search.
cur.append(candidates[i])Add the current candidate to the path.
This 'choose' step explores the branch where the candidate is included, enabling repeated use by not advancing the index.
dfs(0, [], 0)Start the recursive backtracking from the first candidate with an empty path and total zero.
This initiates the entire search process, representing the root of the decision tree.
returnReturn to stop further recursion after finding a valid combination.
This prevents exploring further candidates once the target sum is reached, avoiding invalid or duplicate combinations.
returnReturn to stop recursion on invalid paths.
This halts exploration when no valid combination can be formed from the current state.
return resReturn the list of all valid combinations found.
After recursion completes, this returns the accumulated results to the caller.
res = []Initialize the list to store all valid combinations.
This list accumulates all valid paths found during recursion, serving as the final output container.
Test Your Understanding
What enables the algorithm to reuse the same candidate multiple times in the combinations?
The recursive call that includes the current candidate uses the same index i, allowing the candidate to be chosen repeatedly before moving on to the next candidate.
Related Problems
Backtracking pattern
Don't just read it. Drill it.
Reconstruct Combination Sum from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Combination Sum drill