How do you solve Combination Sum II?

Sort candidates. Use backtracking with parameters (current combination, start index, remaining target). At each recursion, iterate from start to end, skip duplicates by comparing current candidate to previous candidate at the same level, choose candidate, recurse with updated target and next index, then backtrack by removing candidate. Collect combinations when target reaches zero.

What pattern does Combination Sum II use?

The Pattern: Backtracking (State Restoration with Duplicate Pruning) The Heuristic: When generating combinations from a list with duplicates, sort the list and skip over repeated elements at the same recursion depth to avoid duplicate results, ensuring each unique combination is generated exactly once.

Combination Sum II — Backtracking

Q: What is the time complexity of Combination Sum II?

O(2^n). In the worst case, the algorithm explores all subsets of candidates, which is exponential in the number of candidates. Sorting adds O(n log n) but is dominated by backtracking.

Problem

Given a collection of candidate numbers (candidates) and a target number (target), return a list of all unique combinations in candidates where the candidate numbers sum to target. Each number in candidates may only be used once in the combination. The solution set must not contain duplicate combinations.

1 ≤ candidates.length ≤ 100
1 ≤ candidates[i] ≤ 50
1 ≤ target ≤ 30

Example

Input: candidates = [10,1,2,7,6,1,5], target = 8

Output: [[1,1,6],[1,2,5],[1,7],[2,6]]

The algorithm first sorts the candidates to group duplicates together. It then explores combinations recursively, choosing or skipping each candidate while avoiding duplicates by skipping repeated numbers at the same recursion depth. For example, it picks the first '1' at index 1, explores all combinations including it, then skips the second '1' at index 2 to avoid duplicate combinations. This pruning ensures unique combinations without revisiting the same candidate multiple times at the same recursion level.

Approach

Straightforward Solution

A brute-force approach tries all subsets and filters those summing to target, resulting in exponential time and duplicate combinations due to repeated elements.

Core Observation

The problem requires enumerating all unique combinations summing to a target, with each candidate used at most once. The presence of duplicates in candidates means naive recursion can generate duplicate combinations, so careful pruning is necessary.

Path to Optimal

Preview

Sorting candidates groups duplicates, enabling skipping repeated elements at the same recursion depth. The backtracking explores candidates from the current position forward, choosing or skipping each candidate…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Sort candidates. Use backtracking with parameters (current combination, start index, remaining target)…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(2^n)

In the worst case, the algorithm explores all subsets of candidates, which is exponential in the number of candidates. Sorting adds O(n log n) but is dominated by backtracking.

Space

O(n)

The recursion stack and current combination list can grow up to O(n) in the worst case, where n is the number of candidates.

Solution

Python

1class Solution:
  def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:
      candidates.sort()
      res = []
5
      def backtrack(cur, pos, target):
          if target == 0:
              res.append(cur.copy())
              return
          if target <= 0:
              return
          
          prev = -1
          for i in range(pos, len(candidates)):
              if candidates[i] == prev:
                  continue
              
              cur.append(candidates[i])
              backtrack(cur, i + 1, target - candidates[i])
              cur.pop()
              prev = candidates[i]
      
      backtrack([], 0, target)
      return res

Step-by-Step Solution

1

Sort Candidates and Initialize Result Container

3candidates.sort()
4res = []

Objective

To prepare the input for efficient duplicate detection and store the final unique combinations.

Key Insight

Sorting candidates groups duplicates together, which is essential for the pruning step that skips repeated elements at the same recursion depth. Initializing the result list upfront provides a container to accumulate valid combinations found during backtracking.

Interview Quick-Check

Core Logic

Sorting is critical to enable skipping duplicates efficiently during backtracking.

State & Boundaries

The result list must be initialized before recursion to collect all valid combinations.

2

Explore Combinations Recursively with Duplicate Skipping

To systematically build combinations by choosing candidates while avoiding duplicates and pruning invalid paths.

3

Initiate Backtracking and Return Final Results

To start the recursive exploration from the beginning of the sorted candidates and return all unique combinations found.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 15 Critical

if candidates[i] == prev:

Skip the current candidate if it is the same as the previous candidate at this recursion depth.

Skipping duplicates at the same recursion level avoids generating duplicate combinations, ensuring uniqueness in the result set.

Line 20 Critical

cur.pop()

Remove the last candidate from the current combination to backtrack.

Backtracking restores the state to explore alternative branches, ensuring the current path is correctly maintained for other recursive calls.

Line 7 Critical

if target == 0:

Check if the remaining target is exactly zero.

This base case identifies when a valid combination summing to the original target has been found, triggering its addition to the results.

Full line-by-line criticality + rationale for all 18 lines available on Pro.

Test Your Understanding

How does the algorithm avoid generating duplicate combinations when candidates contain repeated numbers?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Combination Sum II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Combination Sum II drill

or drill a free problem

1	`class Solution:`
2	`def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:`
3	`candidates.sort()`
4	`res = []`
5
6	`def backtrack(cur, pos, target):`
7	`if target == 0:`
8	`res.append(cur.copy())`
9	`return`
10	`if target <= 0:`
11	`return`
12
13	`prev = -1`
14	`for i in range(pos, len(candidates)):`
15	`if candidates[i] == prev:`
16	`continue`
17
18	`cur.append(candidates[i])`
19	`backtrack(cur, i + 1, target - candidates[i])`
20	`cur.pop()`
21	`prev = candidates[i]`
22
23	`backtrack([], 0, target)`
24	`return res`