Approach Summary
Backtrack with start index. Can reuse same element (don't advance start). Prune when sum exceeds target.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Pick / Don't Pick Binary Decision Tree | O(2^target) | O(target) call stack | At each index choose either to include the candidate (and stay on it) or advance to next candidate. |
| 2 Approach 2: Pruned Backtracking with Sorting (Optimal) | O(N * 2^target) | O(target) path buffer | Sort candidates first and loop from start index, breaking immediately when candidate > remain. |
Step 1: Baseline
Approach 1: Pick / Don't Pick Binary Decision Tree
Time: O(2^target)
Space: O(target) call stack
Construct a binary recursive state: at index, either pick candidates[index] (reducing target and remaining at index for potential reuse) or skip candidates[index] (moving to index + 1). When target reaches 0, append a copy of current combination. If index == n, terminate branch.
Approach 1: Pick / Don't Pick Binary Decision Tree Implementation
Approach 1: Pick / Don't Pick Binary Decision Tree
class Solution {
public void findCombinationSum(int index, int[] candidates, int target, List<List<Integer>> result, List<Integer> ds) {
if (index == candidates.length) {
if (target == 0) result.add(new ArrayList<>(ds));
return;
}
if (candidates[index] <= target) {
ds.add(candidates[index]);
findCombinationSum(index, candidates, target - candidates[index], result, ds);
ds.remove(ds.size() - 1);
}
findCombinationSum(index + 1, candidates, target, result, ds);
}
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
findCombinationSum(0, candidates, target, result, new ArrayList<>());
return result;
}
}class Solution {
public:
void findCombinationSum(int index, vector<int>& candidates, int target, vector<vector<int>>& result, vector<int>& ds) {
if (index == candidates.size()) {
if (target == 0) result.push_back(ds);
return;
}
if (candidates[index] <= target) {
ds.push_back(candidates[index]);
findCombinationSum(index, candidates, target - candidates[index], result, ds);
ds.pop_back();
}
findCombinationSum(index + 1, candidates, target, result, ds);
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> result;
vector<int> ds;
findCombinationSum(0, candidates, target, result, ds);
return result;
}
};class Solution:
def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
result = []
ds = []
def find_combinations(index, rem):
if index == len(candidates):
if rem == 0:
result.append(list(ds))
return
if candidates[index] <= rem:
ds.append(candidates[index])
find_combinations(index, rem - candidates[index])
ds.pop()
find_combinations(index + 1, rem)
find_combinations(0, target)
return resultfunction combinationSum(candidates, target) {
const result = [];
const ds = [];
function findCombinations(index, rem) {
if (index === candidates.length) {
if (rem === 0) result.push([...ds]);
return;
}
if (candidates[index] <= rem) {
ds.push(candidates[index]);
findCombinations(index, rem - candidates[index]);
ds.pop();
}
findCombinations(index + 1, rem);
}
findCombinations(0, target);
return result;
} Step 2: Most Optimized
Approach 2: Pruned Backtracking with Sorting (Optimal)
Time: O(N * 2^target)
Space: O(target) path buffer
By sorting candidates in ascending order, as soon as candidates[i] > remain, all subsequent elements in the array are also guaranteed to be greater than remain. Breaking the loop immediately eliminates extensive dead-end recursion branches.
Approach 2: Pruned Backtracking with Sorting (Optimal) Implementation
Approach 2: Pruned Backtracking with Sorting (Optimal)
class Solution {
private void backtrack(int[] candidates, int start, int remain, List<Integer> path, List<List<Integer>> result) {
if (remain == 0) {
result.add(new ArrayList<>(path));
return;
}
for (int i = start; i < candidates.length; i++) {
if (candidates[i] > remain) break;
path.add(candidates[i]);
backtrack(candidates, i, remain - candidates[i], path, result);
path.remove(path.size() - 1);
}
}
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> result = new ArrayList<>();
backtrack(candidates, 0, target, new ArrayList<>(), result);
return result;
}
}class Solution {
public:
void backtrack(vector<int>& candidates, int start, int remain, vector<int>& path, vector<vector<int>>& result) {
if (remain == 0) {
result.push_back(path);
return;
}
for (int i = start; i < candidates.size(); i++) {
if (candidates[i] > remain) break;
path.push_back(candidates[i]);
backtrack(candidates, i, remain - candidates[i], path, result);
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<vector<int>> result;
vector<int> path;
backtrack(candidates, 0, target, path, result);
return result;
}
};class Solution:
def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
candidates.sort()
result = []
def backtrack(start, remain, path):
if remain == 0:
result.append(list(path))
return
for i in range(start, len(candidates)):
if candidates[i] > remain:
break
path.append(candidates[i])
backtrack(i, remain - candidates[i], path)
path.pop()
backtrack(0, target, [])
return resultfunction combinationSum(candidates, target) {
candidates.sort((a, b) => a - b);
const result = [];
function backtrack(start, remain, path) {
if (remain === 0) {
result.push([...path]);
return;
}
for (let i = start; i < candidates.length; i++) {
if (candidates[i] > remain) break;
path.push(candidates[i]);
backtrack(i, remain - candidates[i], path);
path.pop();
}
}
backtrack(0, target, []);
return result;
}Edge Cases to Watch
- target is smaller than any candidate (returns empty list immediately)
- Single candidate that divides target (e.g. candidates = [2], target = 6; returns [[2, 2, 2]])
- No combination adds up to target (returns empty list)
- Multiple valid combinations of varying lengths (e.g. [2, 3, 6, 7], target = 7; returns [[2, 2, 3], [7]])
Algorithmic Pattern
View Pattern Guide →
Master the Backtracking Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Backtracking pattern.
Framework: Backtracking • Interview Prep: Tested at FAANG •
Explore all Backtracking problems & invariants →
How to Recognize This Pattern
- Unbounded element selection
- Sum to target
Complexity Analysis
Time Complexity
O(n^(T/M))
Space Complexity
O(T/M)
Tags
Array Backtracking
Frequently Asked Questions
What is the optimal time and space complexity for Combination Sum?
The optimal solution for Combination Sum achieves O(n^(T/M)) runtime complexity and requires O(T/M) auxiliary space. Time complexity is O(2^(target / min(candidates))) in the worst case as the decision tree depth is bounded by target / min(candidates). Space complexity is O(target / min(candidates)) for the recursion stack and current path buffer.
How do I identify that Combination Sum requires the Backtracking pattern?
In technical interviews, look for key problem signals: Unbounded element selection; Sum to target. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Backtracking strategy.
What critical edge cases must be handled in Combination Sum?
Essential edge cases to verify include: target is smaller than any candidate (returns empty list immediately); Single candidate that divides target (e.g. candidates = [2], target = 6; returns [[2, 2, 2]]); No combination adds up to target (returns empty list); Multiple valid combinations of varying lengths (e.g. [2, 3, 6, 7], target = 7; returns [[2, 2, 3], [7]]). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Combination Sum?
Combination Sum is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Facebook, Adobe.