LeetEye LeetEye
Hard Backtracking ~5 min

Combination Sum II

backtracking combination-sum-ii

Problem

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.

Examples

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]]
Key Insight

Combine Combination Sum's target tracking with Subsets II's duplicate skipping.

Combination Sum + Subsets II: move to i+1 (no reuse), skip if same as previous at same level (dedup), break if exceeds target (prune).

How to Approach This Problem

Pattern Recognition: When you see keywords like combination sum ii backtracking, think Backtracking.

Step-by-Step Reasoning

1 After choosing candidates[i], the next recursive call starts at:
Answer: i + 1 (move forward)
Unlike Combination Sum I, each element can only be used once.
2 For candidates = [1,1,2], to avoid duplicate [1,2]:
Answer: Sort and skip same value at same level
Same pattern as Subsets II. Sort, then skip if nums[i] == nums[i-1] at same level.
3 We stop exploring when:
Answer: All of the above
All are valid stopping conditions.
4 We skip candidates[i] if:
Answer: Either A or B
Skip if too large (pruning) or duplicate at same level (dedup).
5 Sorting helps with:
Answer: Both
Sorting enables both optimizations.
6 The key differences from Combination Sum I are:
Answer: Both A and B
Two changes: no reuse (i+1), and deduplication.

Solution

def combinationSum2(candidates: List[int], target: int) -> List[List[int]]:
    candidates.sort()
    result = []
    
    def backtrack(start, current, remaining):
        if remaining == 0:
            result.append(current[:])
            return
        
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break
            if i > start and candidates[i] == candidates[i-1]:
                continue
            current.append(candidates[i])
            backtrack(i + 1, current, remaining - candidates[i])
            current.pop()
    
    backtrack(0, [], target)
    return result

Complexity Analysis

Time O(2^n)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice Backtracking problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye