266. Combination Sum
🔗 LeetCode Problem: 39. Combination Sum
📊 Difficulty: Medium
🏷️ Topics: Array, Backtracking
Problem Statement
Given an array of distinct integers candidates and a target 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. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.
Example 2:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:
Input: candidates = [2], target = 1
Output: []
Constraints:
- 1 <= candidates.length <= 30
- 2 <= candidates[i] <= 40
- All elements of candidates are distinct
- 1 <= target <= 40
🌟 ELI5: The Simple Idea!
Think of it like making change for money:
You have coins: [2, 3, 6, 7]
You want to make: 7
Ways to make 7:
2 + 2 + 3 = 7 ✓
7 = 7 ✓
Can't make 7:
2 + 3 = 5 (not enough)
2 + 6 = 8 (too much)
6 + 3 = 9 (too much)
Key insight: You can use the SAME coin multiple times!
2 + 2 + 3 uses coin "2" twice
The Building Process:
Start with: [] (empty combination)
Target remaining: 7
Try coin 2:
[2], remaining: 7-2 = 5
Try coin 2 again:
[2, 2], remaining: 5-2 = 3
Try coin 2 again:
[2, 2, 2], remaining: 3-2 = 1
Can't use 2 (too big), can't use 3,6,7 (all too big)
Dead end!
Try coin 3:
[2, 2, 3], remaining: 3-3 = 0
Found one! ✓
Continue exploring all possibilities...
🎨 Visual Understanding
Decision Tree for candidates=[2,3,6,7], target=7
[]
target=7
/ | | \
2 3 6 7
/ | | \
[2] [3] [6] [7]
rem=5 rem=4 rem=1 rem=0 ✓
/ | | \ / | \ ✗
2 3 6 7 3 6 7
/ | ✗ ✗ | ✗ ✗
[2,2] [2,3] [3,3]
rem=3 rem=2 rem=-2 ✗
/ | \ / \
2 3 6 3 6
/ | ✗ | ✗
[2,2,2] [2,2,3] [2,3,3]
rem=1 rem=0 ✓ rem=-1 ✗
✗
Valid combinations: [[2,2,3], [7]]
Why No Duplicates?
Without ordering constraint:
[2, 3, 2] and [2, 2, 3] are same combination!
[3, 2, 2] also same!
Solution: Only pick candidates >= last picked
If we picked 2, next can be: 2, 3, 6, 7
If we picked 3, next can be: 3, 6, 7 (not 2!)
If we picked 6, next can be: 6, 7 (not 2 or 3!)
This ensures: [2,2,3] found, but [2,3,2] and [3,2,2] never generated!
🎯 Approach 1: Backtracking (Recursion) ⭐⭐
The Most Common Solution
Algorithm:
Use backtracking with:
- Current combination being built
- Remaining target to achieve
- Start index (to avoid duplicates)
Rules:
1. If remaining == 0 → Found valid combination!
2. If remaining < 0 → Invalid, backtrack
3. Try each candidate from start index onwards
4. Can use same candidate multiple times
Implementation
import java.util.*;
/**
* Backtracking approach
* Time: O(N^(T/M)) where N=candidates.length, T=target, M=min(candidates)
* Space: O(T/M) - Recursion depth
*/
class Solution {
private List<List<Integer>> result;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
result = new ArrayList<>();
backtrack(candidates, target, 0, new ArrayList<>());
return result;
}
// start: index to start picking from (avoids duplicates)
// remaining: how much more we need to reach target
private void backtrack(int[] candidates, int remaining, int start,
List<Integer> current) {
// Base case: found valid combination
if (remaining == 0) {
result.add(new ArrayList<>(current));
return;
}
// Base case: exceeded target
if (remaining < 0) {
return;
}
// Try each candidate from start index
for (int i = start; i < candidates.length; i++) {
// Choose
current.add(candidates[i]);
// Explore (can reuse same candidate, so pass i not i+1)
backtrack(candidates, remaining - candidates[i], i, current);
// Unchoose (backtrack)
current.remove(current.size() - 1);
}
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.combinationSum(new int[]{2,3,6,7}, 7));
System.out.println(sol.combinationSum(new int[]{2,3,5}, 8));
}
}
⏰ Time: O(N^(T/M)) where N=len(candidates), T=target, M=min(candidates)
💾 Space: O(T/M) - Maximum recursion depth
🔍 Super Detailed Dry Run
Example: candidates = [2,3,6,7], target = 7
Goal: Find all combinations that sum to 7
═══════════════════════════════════════════════════════════════
Backtrack Call Tree
═══════════════════════════════════════════════════════════════
Call 1: backtrack([2,3,6,7], remaining=7, start=0, current=[])
remaining=7 (continue)
Loop i=0 (candidate=2):
current = [2]
→ backtrack([2,3,6,7], 5, 0, [2])
═══════════════════════════════════════════════════════════════
Call 2: backtrack([2,3,6,7], remaining=5, start=0, current=[2])
remaining=5 (continue)
Loop i=0 (candidate=2):
current = [2, 2]
→ backtrack([2,3,6,7], 3, 0, [2,2])
═══════════════════════════════════════════════════════════════
Call 3: backtrack([2,3,6,7], remaining=3, start=0, current=[2,2])
remaining=3 (continue)
Loop i=0 (candidate=2):
current = [2, 2, 2]
→ backtrack([2,3,6,7], 1, 0, [2,2,2])
═══════════════════════════════════════════════════════════════
Call 4: backtrack([2,3,6,7], remaining=1, start=0, current=[2,2,2])
remaining=1 (continue)
Loop i=0 (candidate=2):
current = [2, 2, 2, 2]
→ backtrack([2,3,6,7], -1, 0, [2,2,2,2])
═══════════════════════════════════════════════════════════════
Call 5: backtrack([2,3,6,7], remaining=-1, start=0, current=[2,2,2,2])
remaining=-1 < 0 → Return (exceeded target)
[Back to Call 4]
Remove last element: current = [2,2,2]
Loop i=1 (candidate=3):
3 > 1 → Will exceed, skip
Loop i=2,3: All too big, skip
Return
[Back to Call 3]
Remove last element: current = [2,2]
Loop i=1 (candidate=3):
current = [2, 2, 3]
→ backtrack([2,3,6,7], 0, 1, [2,2,3])
═══════════════════════════════════════════════════════════════
Call 6: backtrack([2,3,6,7], remaining=0, start=1, current=[2,2,3])
remaining=0 → Found valid combination!
Add [2,2,3] to result ✓
Return
Result: [[2,2,3]]
[Back to Call 3]
Remove last element: current = [2,2]
Loop i=2 (candidate=6):
6 > 3 → Skip
Loop i=3 (candidate=7):
7 > 3 → Skip
Return
[Back to Call 2]
Remove last element: current = [2]
Loop i=1 (candidate=3):
current = [2, 3]
→ backtrack([2,3,6,7], 2, 1, [2,3])
═══════════════════════════════════════════════════════════════
Call 7: backtrack([2,3,6,7], remaining=2, start=1, current=[2,3])
remaining=2 (continue)
Loop i=1 (candidate=3):
3 > 2 → Skip
Loop i=2,3: All too big, skip
Return
[Back to Call 2]
Remove last element: current = [2]
Loop i=2,3: Candidates 6,7 too big, skip
Return
[Back to Call 1]
Remove last element: current = []
Loop i=1 (candidate=3):
current = [3]
→ backtrack([2,3,6,7], 4, 1, [3])
... (Similar exploration for candidates 3, 6, 7)
═══════════════════════════════════════════════════════════════
Eventually reach:
Call N: backtrack([2,3,6,7], remaining=7, start=3, current=[])
Loop i=3 (candidate=7):
current = [7]
→ backtrack([2,3,6,7], 0, 3, [7])
remaining=0 → Found valid combination!
Add [7] to result ✓
═══════════════════════════════════════════════════════════════
Final Result: [[2,2,3], [7]]
Visual Decision Tree:
([], 7)
/ | \
2 3 7
/ | \
([2],5) ([3],4) ([7],0) ✓
/ \ |
2 3 3,6,7
/ \ (all exceed)
([2,2],3) ([2,3],2)
/ \ |
2 3 3,6,7
/ \ (all exceed)
([2,2,2],1) ([2,2,3],0) ✓
|
2,3,6,7
(all exceed)
🎯 Approach 2: Backtracking with Pruning ⭐
Optimized Version
Key optimization: Sort candidates first, then break early when candidate exceeds remaining.
import java.util.*;
class Solution {
private List<List<Integer>> result;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
result = new ArrayList<>();
Arrays.sort(candidates); // Sort for pruning
backtrack(candidates, target, 0, new ArrayList<>());
return result;
}
private void backtrack(int[] candidates, int remaining, int start,
List<Integer> current) {
if (remaining == 0) {
result.add(new ArrayList<>(current));
return;
}
for (int i = start; i < candidates.length; i++) {
// Pruning: if current candidate exceeds remaining,
// all later candidates will too (array is sorted)
if (candidates[i] > remaining) {
break; // No need to continue
}
current.add(candidates[i]);
backtrack(candidates, remaining - candidates[i], i, current);
current.remove(current.size() - 1);
}
}
}
Benefits: - Early termination when candidate > remaining - Fewer recursive calls - Same time complexity worst case, but faster in practice
🎯 Approach 3: Iterative (Using Stack) ⭐
Alternative Solution
import java.util.*;
class Solution {
static class State {
List<Integer> combination;
int remaining;
int start;
State(List<Integer> combination, int remaining, int start) {
this.combination = new ArrayList<>(combination);
this.remaining = remaining;
this.start = start;
}
}
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Stack<State> stack = new Stack<>();
stack.push(new State(new ArrayList<>(), target, 0));
while (!stack.isEmpty()) {
State current = stack.pop();
// Found valid combination
if (current.remaining == 0) {
result.add(current.combination);
continue;
}
// Try each candidate from start index
for (int i = current.start; i < candidates.length; i++) {
int candidate = candidates[i];
// Skip if exceeds remaining
if (candidate > current.remaining) {
continue;
}
// Create new state with this candidate
List<Integer> newCombination = new ArrayList<>(current.combination);
newCombination.add(candidate);
stack.push(new State(
newCombination,
current.remaining - candidate,
i // Can reuse same candidate
));
}
}
return result;
}
}
⏰ Time: O(N^(T/M))
💾 Space: O(N^(T/M)) - Stack can hold many states
⚠️ Common Mistakes
Mistake 1: Not avoiding duplicates
// ❌ WRONG - Generates duplicates like [2,3] and [3,2]
backtrack(candidates, remaining - candidates[i], 0, current);
// Always starts from index 0!
// ✓ CORRECT - Pass current index to avoid going back
backtrack(candidates, remaining - candidates[i], i, current);
// Can reuse current candidate, but won't pick earlier ones
Mistake 2: Forgetting to copy list when adding to result
// ❌ WRONG - Adds reference, gets modified later!
if (remaining == 0) {
result.add(current); // Reference to same list!
return;
}
// ✓ CORRECT - Add a copy
if (remaining == 0) {
result.add(new ArrayList<>(current));
return;
}
Mistake 3: Not backtracking properly
// ❌ WRONG - Doesn't remove after exploring
current.add(candidates[i]);
backtrack(candidates, remaining - candidates[i], i, current);
// current still has the added element!
// ✓ CORRECT - Remove after exploring
current.add(candidates[i]);
backtrack(candidates, remaining - candidates[i], i, current);
current.remove(current.size() - 1); // Backtrack!
Mistake 4: Wrong index increment
// ❌ WRONG - Can't reuse same number
backtrack(candidates, remaining - candidates[i], i + 1, current);
// Moves to next candidate, can't reuse current one
// ✓ CORRECT - Pass i to allow reuse
backtrack(candidates, remaining - candidates[i], i, current);
Mistake 5: Not handling base case properly
// ❌ WRONG - Doesn't check if exceeded
if (remaining == 0) {
result.add(new ArrayList<>(current));
return;
}
// Will recurse with negative remaining!
// ✓ CORRECT - Check both conditions
if (remaining == 0) {
result.add(new ArrayList<>(current));
return;
}
if (remaining < 0) {
return; // Exceeded target
}
🎯 Pattern Recognition
Problem Type: Combination Generation with Reuse
Core Pattern: Backtracking + Index Tracking
When to Apply:
✓ Find all combinations that meet criteria
✓ Can reuse elements unlimited times
✓ Need to avoid duplicate combinations
✓ Target sum or goal to achieve
Recognition Keywords:
- "all combinations"
- "sum to target"
- "unlimited number of times"
- "unique combinations"
- "distinct integers"
Similar Problems:
- Combination Sum II (LC 40) - Can't reuse, has duplicates
- Combination Sum III (LC 216) - Fixed number of elements
- Combination Sum IV (LC 377) - Count combinations (DP)
- Coin Change (LC 322) - Minimum coins (DP)
Key Components:
┌────────────────────────────────────────────┐
│ Backtracking: Explore all valid paths │
│ Start index: Avoid duplicate combinations │
│ Reuse: Pass same index (i not i+1) │
│ Pruning: Break if candidate > remaining │
│ Base case: remaining == 0 or < 0 │
│ Time: O(N^(T/M)), Space: O(T/M) │
└────────────────────────────────────────────┘
🧠 Interview Strategy
Step 1: "This is a backtracking problem with unlimited reuse"
Step 2: "Need to find all combinations that sum to target"
Step 3: "Use start index to avoid duplicates like [2,3] vs [3,2]"
Key Points to Mention:
- Backtracking explores all valid combinations
- Start index ensures we don't generate duplicates
- Pass same index i (not i+1) to allow reuse
- Base cases: remaining == 0 (success), < 0 (fail)
- Can optimize with sorting and early break
Walk Through Example:
"For candidates=[2,3,6,7], target=7:
Start with empty []
Try 2: [2], remaining=5
Try 2 again: [2,2], remaining=3
Try 3: [2,2,3], remaining=0 → Found! ✓
Try 7: [7], remaining=0 → Found! ✓
Result: [[2,2,3], [7]]"
Why Start Index:
"Without start index, we'd generate:
[2,3] and [3,2] - these are same combination!
With start index i:
If we picked candidate[1]=3, next pick from index 1 onwards
This ensures we only get [2,3], never [3,2]"
Complexity:
"Time is O(N^(T/M)) where:
N = number of candidates
T = target value
M = minimum candidate
Worst case: all 1s summing to T
Space is O(T/M) for recursion depth"
Edge Cases to Mention:
✓ Target = 0 → [[]]
✓ No valid combination → []
✓ Single candidate equals target → [[target]]
✓ Can reuse same number multiple times
📝 Quick Revision Notes
🎯 Core Concept:
Combination Sum: Use backtracking to find all combinations summing to target. Can reuse same number unlimited times. Use start index to avoid duplicates like [2,3] vs [3,2]. Pass same index i (not i+1) to allow reuse. Base case: remaining == 0.
⚡ Quick Implementation:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
public class Solution {
static class State {
ArrayList<Integer> currList;
int remaining;
int currIndex;
public State(ArrayList<Integer> currList, int remaining, int currIndex) {
this.currList = currList;
this.remaining = remaining;
this.currIndex = currIndex;
}
}
public List<List<Integer>> combinationSum(int[] a, int k) {
// return recursive(a, k);
// return recursiveWithSort(a, k);
return iterative(a, k);
}
private List<List<Integer>> iterative(int[] a, int k) {
List<List<Integer>> res = new ArrayList<>();
// step 1: sort the array
Arrays.sort(a);
// step 2: initialize the current state of the stack
Stack<State> stack = new Stack<>();
stack.push(new State(new ArrayList<>(), k, 0));
// step 3: process till stack becomes empty
while (!stack.isEmpty()) {
State currState = stack.pop();
ArrayList<Integer> currList = currState.currList;
int remaining = currState.remaining;
int currIndex = currState.currIndex;
if (remaining == 0) {
res.add(new ArrayList<>(currList));
continue;
}
if (remaining < 0) {
continue;
}
for (int i = currIndex; i < a.length; i++) {
if (remaining - a[i] >= 0) {
currList.add(a[i]);
// GOTCHA: you need to create new list while pushing to stack (same as string)
stack.push(new State(new ArrayList<>(currList), remaining - a[i], i));
currList.remove(currList.size() - 1);
} else {
continue;
}
}
}
return res;
}
private List<List<Integer>> recursiveWithSort(int[] a, int k) {
List<List<Integer>> res = new ArrayList<>();
// step 1: sort the numbers
// why? refer step 3 of prev method
// You do not need to check every number once k < 0 if the
// numbers are sorted. Refer step 2.
// Note: all other steps are exactly same.
Arrays.sort(a);
recursiveWithSortUtil(a, k, 0, new ArrayList<>(), res);
return res;
}
private void recursiveWithSortUtil(int[] a, int k, int currIndex, ArrayList<Integer> currList,
List<List<Integer>> res) {
if (k == 0) {
res.add(new ArrayList<>(currList));
return;
}
if (k < 0) {
return;
}
// step 2: no need to proceed further to try other numbers
// remaining in the array if k - a[i] >= 0
for (int i = currIndex; i < a.length; i++) {
if (k - a[i] >= 0) {
currList.add(a[i]);
recursiveWithSortUtil(a, k - a[i], i, currList, res);
currList.remove(currList.size() - 1);
} else {
return;
}
}
}
private List<List<Integer>> recursive(int[] a, int k) {
List<List<Integer>> res = new ArrayList<>();
recursiveUtil(a, k, 0, new ArrayList<>(), res);
return res;
}
private void recursiveUtil(int[] a, int k, int currIndex, ArrayList<Integer> currList, List<List<Integer>> res) {
// step 5: base case 1
if (k == 0) {
res.add(new ArrayList<>(currList));
return;
}
// step 6: base case 2
if (k < 0) {
return;
}
// step 1: try the element at index currIndex
for (int i = currIndex; i < a.length; i++) {
// step 2: add it to the curr list which may becomes one of the result
currList.add(a[i]);
// step 3: try adding 1 more time the same element (a[i]) with k reduced
// if k becomes negative, you should not try this number at index i
// and you should try for next index which is i+1. See step 5 base case 2
recursiveUtil(a, k - a[i], i, currList, res);
// step 4: remove the added number from the curr list
currList.remove(currList.size() - 1);
}
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.combinationSum(new int[] { 2, 3, 6, 7 }, 7)); // [[2,2,3],[7]]
}
}
🔑 Key Insights:
- Pattern: Backtracking + Start Index
- Reuse: Pass i not i+1 (allows same number again)
- No Duplicates: Start index ensures [2,3] found, not [3,2]
- Base Case: remaining == 0 (success), < 0 (fail)
- Optimization: Sort + break when candidate > remaining
- Time: O(N^(T/M)), Space: O(T/M) ✓
🎪 Memory Aid:
"Try each coin, can reuse same, track from where you came!"
"Pass i not i+1, avoid going back, sum to zero done!" ✨
⚠️ Critical Difference:
ALLOWING REUSE:
backtrack(candidates, remaining - candidates[i], i, current)
Pass i → Can pick candidates[i] again
Example: [2] → can try 2 again → [2,2]
NOT ALLOWING REUSE:
backtrack(candidates, remaining - candidates[i], i+1, current)
Pass i+1 → Must pick next candidate
Example: [2] → must try 3,6,7 next, not 2
This problem: ALLOWS REUSE → Pass i ✓
🧪 Edge Cases
Case 1: Single candidate equals target
Input: candidates = [7], target = 7
Output: [[7]]
Direct match
Case 2: No valid combination
Input: candidates = [2], target = 1
Output: []
Can't make 1 with 2
Case 3: Multiple reuse needed
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
[2,2,2,2] uses 2 four times!
Case 4: Target = smallest candidate
Input: candidates = [2,3,6,7], target = 2
Output: [[2]]
Only one way
All handled correctly! ✓
🎓 Complexity Analysis
Time Complexity: O(N^(T/M))
Where:
N = number of candidates
T = target value
M = minimum candidate value
Why?
Maximum depth of recursion tree: T/M
(If we always pick smallest candidate)
At each level, we branch N ways
Total nodes: N^(T/M)
Example:
candidates = [2,3], target = 8
Min candidate M = 2
Max depth = 8/2 = 4
Branches = 2 (candidates count)
Nodes ≈ 2^4 = 16
Worst case:
candidates = [1], target = 100
Depth = 100
Extremely slow!
Space Complexity: O(T/M)
Recursion stack depth:
Maximum depth = T/M
(Building combination one element at a time)
Each call: O(1) space
Total: O(T/M)
Example:
target = 8, min candidate = 2
Max depth = 4
Space = O(4)
📚 Related Problems
Same Core Pattern: - Combination Sum II (LC 40) - Each number used once, has duplicates - Combination Sum III (LC 216) - Fixed k numbers, use 1-9 - Combination Sum IV (LC 377) - Count ways (DP, order matters)
Similar Backtracking: - Permutations (LC 46) - All permutations - Subsets (LC 78) - All subsets - Letter Combinations (LC 17) - Phone number mapping
Related DP: - Coin Change (LC 322) - Minimum coins to make amount - Coin Change 2 (LC 518) - Number of ways to make amount
Happy practicing! 🎯
Note: This is a classic backtracking problem! Master this and you understand: (1) combination generation, (2) avoiding duplicates with start index, (3) allowing element reuse, (4) pruning for optimization. Very common at FAANG! The "start index" technique is crucial - it appears in many problems! 💪✨