267. Combination Sum II
🔗 LeetCode Problem: 40. Combination Sum II
📊 Difficulty: Medium
🏷️ Topics: Array, Backtracking
Problem Statement
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: [[1,1,6],[1,2,5],[1,7],[2,6]]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5
Output: [[1,2,2],[5]]
Constraints:
- 1 <= candidates.length <= 100
- 1 <= candidates[i] <= 50
- 1 <= target <= 30
🌟 ELI5: The Simple Idea!
Think of it like Combination Sum, but with TWO new rules:
Combination Sum I:
candidates = [2, 3, 6, 7], target = 7
Can reuse: [2, 2, 3] ✓ (uses 2 twice)
No duplicates in array
Combination Sum II:
candidates = [10,1,2,7,6,1,5], target = 8
Can't reuse: Each number used at most once
Has duplicates: Two 1's in array!
New challenges:
1. Can't reuse same index
2. Must avoid duplicate combinations from duplicate values
The Problem with Duplicates:
Input: [1, 1, 2], target = 3
Without handling duplicates:
Pick 1 at index 0: [1] → Pick 2: [1,2] ✓
Pick 1 at index 1: [1] → Pick 2: [1,2] ✓ (DUPLICATE!)
We'd get [[1,2], [1,2]] - Same combination twice!
Solution: Skip duplicate values at same recursion level
"If candidates[i] == candidates[i-1], skip it"
(Only at same level, not in same path)
🎨 Visual Understanding
Decision Tree for candidates=[1,1,2], target=3
Without handling duplicates (WRONG):
[]
/ | \
1₀ 1₁ 2
/ | \
[1₀] [1₁] [2]
/ \ / \ |
1₁ 2 1₀ 2 ✗
/ \ | | |
[1₀,1₁] [1₀,2] [1₁,1₀] [1₁,2]
✗ ✓ ✗ ✓
Result: [[1,2], [1,2]] ✗ DUPLICATES!
With handling duplicates (CORRECT):
[]
/ | \
1₀ 1₁✗ 2
/ skip \
[1₀] [2]
/ \ |
1₁ 2 ✗
/ \
[1₀,1₁] [1₀,2]
✗ ✓
Result: [[1,2]] ✓ NO DUPLICATES!
Key: At same level, skip 1₁ because 1₁ == 1₀
The Duplicate Skipping Rule
SORT FIRST: [1, 1, 2]
At recursion level (choosing from remaining candidates):
i=0: candidates[0] = 1 → Process ✓
i=1: candidates[1] = 1 → Skip! (same as i=0 at this level)
i=2: candidates[2] = 2 → Process ✓
Check: if (i > start && candidates[i] == candidates[i-1]) skip
Why i > start?
- i == start: First element at this level, always process
- i > start: Not first, check if duplicate of previous
🎯 Approach 1: Backtracking with Duplicate Handling ⭐⭐
The Most Common Solution
Algorithm:
1. SORT the candidates array (crucial!)
2. Use backtracking with:
- Current combination being built
- Remaining target
- Start index
3. Skip duplicates at same recursion level:
if (i > start && candidates[i] == candidates[i-1]) continue
4. Move to next index (i+1) - can't reuse same element
Implementation
import java.util.*;
/**
* Backtracking with duplicate handling
* Time: O(2^n) - Each element: include or exclude
* Space: O(n) - Recursion depth
*/
class Solution {
private List<List<Integer>> result;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
result = new ArrayList<>();
Arrays.sort(candidates); // CRUCIAL: Sort to group duplicates
backtrack(candidates, target, 0, new ArrayList<>());
return result;
}
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;
}
// Try each candidate from start index
for (int i = start; i < candidates.length; i++) {
// Skip duplicates at same recursion level
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
// Pruning: if current candidate exceeds remaining, stop
if (candidates[i] > remaining) {
break;
}
// Choose
current.add(candidates[i]);
// Explore (i+1: can't reuse same element)
backtrack(candidates, remaining - candidates[i], i + 1, current);
// Unchoose (backtrack)
current.remove(current.size() - 1);
}
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.combinationSum2(new int[]{10,1,2,7,6,1,5}, 8));
System.out.println(sol.combinationSum2(new int[]{2,5,2,1,2}, 5));
}
}
⏰ Time: O(2^n) - Each element can be included or excluded
💾 Space: O(n) - Maximum recursion depth
🔍 Super Detailed Dry Run
Example: candidates = [1,1,2], target = 3
Step 0: Sort candidates
[1, 1, 2] → Already sorted
═══════════════════════════════════════════════════════════════
Backtrack Call Tree
═══════════════════════════════════════════════════════════════
Call 1: backtrack([1,1,2], remaining=3, start=0, current=[])
remaining=3 (continue)
Loop i=0:
i=0, start=0 → i == start, process
candidates[0]=1, check: 1 <= 3 ✓
current = [1]
→ backtrack([1,1,2], 2, 1, [1])
═══════════════════════════════════════════════════════════════
Call 2: backtrack([1,1,2], remaining=2, start=1, current=[1])
remaining=2 (continue)
Loop i=1:
i=1, start=1 → i == start, process
candidates[1]=1, check: 1 <= 2 ✓
current = [1, 1]
→ backtrack([1,1,2], 1, 2, [1,1])
═══════════════════════════════════════════════════════════════
Call 3: backtrack([1,1,2], remaining=1, start=2, current=[1,1])
remaining=1 (continue)
Loop i=2:
i=2, start=2 → i == start, process
candidates[2]=2, check: 2 > 1 ✗
Break (pruning)
Return
[Back to Call 2]
Remove last: current = [1]
Loop i=2:
i=2, start=1 → i > start, check for duplicate
candidates[2]=2, candidates[1]=1
2 != 1 → Not duplicate, process
candidates[2]=2, check: 2 <= 2 ✓
current = [1, 2]
→ backtrack([1,1,2], 0, 3, [1,2])
═══════════════════════════════════════════════════════════════
Call 4: backtrack([1,1,2], remaining=0, start=3, current=[1,2])
remaining=0 → Found valid combination!
Add [1, 2] to result ✓
Return
Result: [[1,2]]
[Back to Call 2]
Remove last: current = [1]
Loop finished
Return
[Back to Call 1]
Remove last: current = []
Loop i=1:
i=1, start=0 → i > start, check for duplicate
candidates[1]=1, candidates[0]=1
1 == 1 → DUPLICATE! Skip this iteration ✓✓✓
continue (DON'T PROCESS)
Loop i=2:
i=2, start=0 → i > start, check for duplicate
candidates[2]=2, candidates[1]=1
2 != 1 → Not duplicate, process
candidates[2]=2, check: 2 <= 3 ✓
current = [2]
→ backtrack([1,1,2], 1, 3, [2])
═══════════════════════════════════════════════════════════════
Call 5: backtrack([1,1,2], remaining=1, start=3, current=[2])
remaining=1 (continue)
start=3 >= length=3
Loop doesn't execute
Return
[Back to Call 1]
Remove last: current = []
Loop finished
═══════════════════════════════════════════════════════════════
Final Result: [[1,2]]
Key observation:
At Call 1, when i=1 (second 1):
We skip it because candidates[1] == candidates[0]
This prevents generating duplicate [1,2] from second 1!
Visual with Duplicate Skipping:
([], 3)
/ \
1₀ 1₁ SKIP!
/
([1₀],2)
/ \
1₁ 2
/ \
([1₀,1₁],1) ([1₀,2],0) ✓
|
2 (too big)
Only one valid path: [1₀,2]
Second 1 skipped at root level → No duplicate!
🎯 Approach 2: Alternative - Using Set ⭐
Less Efficient but Easier to Understand
import java.util.*;
class Solution {
private Set<List<Integer>> resultSet;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
resultSet = new HashSet<>();
Arrays.sort(candidates);
backtrack(candidates, target, 0, new ArrayList<>());
return new ArrayList<>(resultSet);
}
private void backtrack(int[] candidates, int remaining, int start,
List<Integer> current) {
if (remaining == 0) {
resultSet.add(new ArrayList<>(current)); // Set handles duplicates
return;
}
for (int i = start; i < candidates.length; i++) {
if (candidates[i] > remaining) break;
current.add(candidates[i]);
backtrack(candidates, remaining - candidates[i], i + 1, current);
current.remove(current.size() - 1);
}
}
}
Pros: Simpler logic (Set automatically removes duplicates)
Cons: Slower (Set operations have overhead)
🎯 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>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates);
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++) {
// Skip duplicates at same level
if (i > current.start && candidates[i] == candidates[i - 1]) {
continue;
}
int candidate = candidates[i];
// Skip if exceeds remaining
if (candidate > current.remaining) {
break;
}
// Create new state
List<Integer> newCombination = new ArrayList<>(current.combination);
newCombination.add(candidate);
stack.push(new State(
newCombination,
current.remaining - candidate,
i + 1 // Can't reuse same element
));
}
}
return result;
}
}
⏰ Time: O(2^n)
💾 Space: O(2^n) - Stack can hold many states
⚠️ Common Mistakes
Mistake 1: Not sorting the array
// ❌ WRONG - Can't identify duplicates without sorting
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
// No sorting!
backtrack(candidates, target, 0, new ArrayList<>());
}
// candidates = [1,2,1] → Can't tell 1's are together
// ✓ CORRECT - Sort first
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates); // [1,1,2] now grouped!
backtrack(candidates, target, 0, new ArrayList<>());
}
Mistake 2: Wrong duplicate check condition
// ❌ WRONG - Always skips duplicates, even in same path
if (candidates[i] == candidates[i - 1]) {
continue;
}
// Would skip [1₀,1₁,2] because 1₁ == 1₀
// ✓ CORRECT - Only skip at same recursion level
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
// i > start ensures we only skip at same level, not in path
Mistake 3: Passing wrong index
// ❌ WRONG - Allows reusing same element
backtrack(candidates, remaining - candidates[i], i, current);
// Can pick same element multiple times!
// ✓ CORRECT - Move to next element
backtrack(candidates, remaining - candidates[i], i + 1, current);
// Each element used at most once
Mistake 4: Not checking i-1 bounds
// ❌ WRONG - Array out of bounds when i=0
if (candidates[i] == candidates[i - 1]) {
continue;
}
// When i=0, i-1 = -1 → Error!
// ✓ CORRECT - Check i > start first
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
Mistake 5: Forgetting to copy list
// ❌ WRONG - All results point to same list!
if (remaining == 0) {
result.add(current); // Reference!
return;
}
// ✓ CORRECT - Add a copy
if (remaining == 0) {
result.add(new ArrayList<>(current));
return;
}
🎯 Pattern Recognition
Problem Type: Combination with No Reuse + Duplicates
Core Pattern: Backtracking + Skip Duplicates at Same Level
When to Apply:
✓ Find all combinations (no reuse)
✓ Input has duplicate values
✓ Must avoid duplicate combinations
✓ Sum to target or meet criteria
Recognition Keywords:
- "each number used once"
- "may contain duplicates"
- "unique combinations"
- "solution set must not contain duplicates"
Differences from Combination Sum I:
┌─────────────────┬──────────────┬──────────────┐
│ Feature │ Sum I │ Sum II │
├─────────────────┼──────────────┼──────────────┤
│ Reuse element │ Yes (pass i) │ No (i+1) │
│ Duplicates │ No │ Yes │
│ Skip logic │ Not needed │ CRUCIAL! │
│ Sort needed │ Optional │ MANDATORY │
└─────────────────┴──────────────┴──────────────┘
Similar Problems:
- Combination Sum (LC 39) - Can reuse, no duplicates
- Combination Sum III (LC 216) - Fixed k numbers
- Subsets II (LC 90) - All subsets with duplicates
Key Components:
┌────────────────────────────────────────────┐
│ Backtracking: Explore all combinations │
│ SORT: Group duplicate values together │
│ Skip: if (i > start && arr[i]==arr[i-1]) │
│ No Reuse: Pass i+1 (not i) │
│ Pruning: Break if candidate > remaining │
│ Time: O(2^n), Space: O(n) │
└────────────────────────────────────────────┘
🧠 Interview Strategy
Step 1: "This is Combination Sum II - no reuse, has duplicates"
Step 2: "I need to sort first, then skip duplicates at same level"
Step 3: "Key difference: pass i+1 (not i) and skip duplicate check"
Key Points to Mention:
- MUST sort array first to group duplicates
- Skip duplicates at same recursion level only
- Check: i > start && candidates[i] == candidates[i-1]
- Pass i+1 (not i) because can't reuse same element
- Same pruning optimization as Combination Sum I
Walk Through Example:
"For candidates=[1,1,2], target=3:
Sort: [1,1,2]
Start with []
Try 1 at i=0: [1]
Try 1 at i=1: [1,1] → remaining=-1, invalid
Try 2 at i=2: [1,2] → remaining=0, found! ✓
Try 1 at i=1: SKIP! (duplicate of i=0 at same level)
Try 2 at i=2: [2] → remaining=1, can't complete
Result: [[1,2]]"
Why Skip Works:
"After trying all combinations starting with 1 at i=0,
trying 1 at i=1 would generate duplicate combinations.
Example: [1₀,2] already found
[1₁,2] would be duplicate!
By skipping 1₁ at root level, we prevent this."
Complexity:
"Time is O(2^n) - each element: include or exclude
Space is O(n) for recursion depth
Sorting adds O(n log n) but doesn't affect overall"
Edge Cases to Mention:
✓ All duplicates: [1,1,1], target=3 → [[1,1,1]]
✓ No valid combination → []
✓ Single element equals target → [[element]]
📝 Quick Revision Notes
🎯 Core Concept:
Combination Sum II: Similar to Combination Sum I but: (1) Can't reuse same element (pass i+1 not i), (2) Array has duplicates (must sort + skip duplicates at same level). Key check: if (i > start && candidates[i] == candidates[i-1]) continue.
⚡ 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>> combinationSum2(int[] a, int k) {
// Naive recursion will not work here because of duplicates
// which need to be skipped
// return recursive(a, k);
// These 2 approaches are same as earlier Combination Sum except 2 GOTCHAs
// return recursiveWithSort(a, k);
return iterative(a, k);
}
private List<List<Integer>> iterative(int[] a, int k) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(a);
Stack<State> stack = new Stack<>();
stack.push(new State(new ArrayList<>(), k, 0));
while (!stack.isEmpty()) {
State currState = stack.pop();
ArrayList<Integer> currList = currState.currList;
int remaining = currState.remaining;
int currIndex = currState.currIndex;
// All below code is exactly same as recursive code
if (remaining == 0) {
res.add(new ArrayList<>(currList));
continue;
}
if (remaining < 0) {
continue;
}
for (int i = currIndex; i < a.length; i++) {
if (i > currIndex && a[i] == a[i - 1]) {
continue;
}
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 + 1));
currList.remove(currList.size() - 1);
} else {
continue;
}
}
}
return res;
}
private List<List<Integer>> recursiveWithSort(int[] a, int k) {
List<List<Integer>> res = new ArrayList<>();
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;
}
for (int i = currIndex; i < a.length; i++) {
// GOTCHA: why i > currIndex? and alsi i + 1 in next call?
// We should not include again the same element as told
// in the question that duplicates need to be skipped.
if (i > currIndex && a[i] == a[i - 1]) {
continue;
}
if (k - a[i] >= 0) {
currList.add(a[i]);
// GOTCHA: why i + 1?
recursiveWithSortUtil(a, k - a[i], i + 1, currList, res);
currList.remove(currList.size() - 1);
} else {
return;
}
}
}
public static void main(String[] args) {
Solution s = new Solution();
// [[1,1,6], [1,2,5], [1,7], [2,6]]
System.out.println(s.combinationSum2(new int[] { 10, 1, 2, 7, 6, 1, 5 }, 8));
}
}
🔑 Key Insights:
- Pattern: Backtracking + Skip Duplicates
- MUST SORT: Groups duplicates together
- Skip Logic:
if (i > start && arr[i] == arr[i-1]) continue - No Reuse: Pass i+1 (not i)
- Why i > start: Allows duplicates in same path, skips at same level
- Time: O(2^n), Space: O(n) ✓
🎪 Memory Aid:
"Sort first, skip duplicate, pass i+1 not i!"
"i > start avoids same level, allows same path!" ✨
⚠️ Critical Difference:
COMBINATION SUM I:
candidates = [2,3,6,7] (no duplicates)
Can reuse: pass i
No skip logic needed
COMBINATION SUM II:
candidates = [1,1,2] (has duplicates)
Can't reuse: pass i+1
MUST skip: if (i > start && arr[i] == arr[i-1])
The skip condition:
i > start → Not first at this level
arr[i] == arr[i-1] → Duplicate value
Prevents: [1₀,2] and [1₁,2] both appearing
Allows: [1₀,1₁,2] in same path ✓
🎯 Why "i > start" not "i > 0":
Example: [1,1,2], target=3
Using i > 0 (WRONG):
Path: [] → [1₀]
At level with start=1:
i=1: candidates[1]=1
Check: i > 0? YES, 1==1? YES
SKIP → Can't build [1₀,1₁,2]!
Using i > start (CORRECT):
Path: [] → [1₀]
At level with start=1:
i=1: candidates[1]=1
Check: i > start? NO (1==1)
PROCESS → Can build [1₀,1₁,2] ✓
🧪 Edge Cases
Case 1: All duplicates
Input: candidates = [1,1,1], target = 3
Output: [[1,1,1]]
All three used
Case 2: No valid combination
Input: candidates = [2], target = 1
Output: []
Can't make 1 with 2
Case 3: Multiple duplicate sets
Input: candidates = [2,5,2,1,2], target = 5
Output: [[1,2,2],[5]]
Handles three 2's correctly
Case 4: Single element equals target
Input: candidates = [1,2,7], target = 7
Output: [[7]]
Direct match
All handled correctly! ✓
🎓 Complexity Analysis
Time Complexity: O(2^n)
Where n = length of candidates
Why?
For each element, two choices:
1. Include it in combination
2. Exclude it from combination
Decision tree has depth n
Each level branches up to 2 ways
Total nodes ≈ 2^n
Example:
candidates = [1,2,3], target = 6
Each element: include or skip
Max combinations: 2^3 = 8
Note: Pruning reduces actual complexity
But worst case is still O(2^n)
Space Complexity: O(n)
Recursion stack depth:
Maximum depth = n
(Building combination one element at a time)
Each call: O(1) space
Total: O(n)
Sorting:
Arrays.sort(): O(n log n) time
But doesn't affect space
📚 Related Problems
Same Core Pattern: - Combination Sum (LC 39) - Can reuse, no duplicates - Combination Sum III (LC 216) - Fixed k numbers, use 1-9 - Subsets II (LC 90) - All subsets with duplicates (same skip logic!)
Similar Skip Logic: - Permutations II (LC 47) - Permutations with duplicates - Subsets II (LC 90) - Subsets with duplicates
Related Backtracking: - Permutations (LC 46) - All permutations - Subsets (LC 78) - All subsets
Happy practicing! 🎯
Note: This problem teaches the crucial "skip duplicates at same level" technique! The condition i > start && arr[i] == arr[i-1] appears in many problems with duplicates. Master this and you can solve: Subsets II, Permutations II, and many more! The key is understanding WHY we use i > start instead of i > 0 - it allows duplicates in the same path while preventing duplicates at the same recursion level! 💪✨