Combination Sum II

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.

Q: 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.

Medium 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

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. By tracking the previous candidate chosen at the same recursion level and skipping duplicates, the algorithm avoids generating duplicate combinations.

Optimal Approach

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.

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.

Pattern Spotlight

Backtracking (State Restoration with Duplicate Pruning)

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.

Solution

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

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.

Explore Combinations Recursively with Duplicate Skipping

6def 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]

Objective

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

Key Insight

The backtracking function explores candidates starting from a given position, choosing each candidate once and recursing with the updated target and next position. By tracking the previous candidate chosen at the current recursion level and skipping candidates equal to it, the algorithm avoids duplicate combinations. The base cases handle when the target is met or exceeded, terminating recursion appropriately. The 'choose, recurse, un-choose' pattern ensures state restoration for exploring alternative branches.

Interview Quick-Check

Core Logic

Backtracking uses recursion with pruning: skip duplicates at the same recursion depth and stop exploring when target is zero or negative.

State & Boundaries

Base cases ensure recursion stops when a valid combination is found or when the target is overshot.

Common Pitfalls & Bugs

Failing to skip duplicates leads to repeated combinations; forgetting to backtrack (pop) corrupts the current path state.

Initiate Backtracking and Return Final Results

23backtrack([], 0, target)
24return res

Objective

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

Key Insight

The initial call to backtracking sets the recursion in motion with an empty current combination, starting index zero, and the full target. Returning the accumulated results after recursion completes provides the final answer. This step connects the setup and recursive exploration phases.

Interview Quick-Check

Core Logic

Starting backtracking from index 0 with an empty path and full target ensures all combinations are explored.

State & Boundaries

Returning the result list after recursion completes provides the final solution.

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.

Line 8 Critical

res.append(cur.copy())

Append a copy of the current combination to the results list.

Copying the current combination is essential because the list is mutated during backtracking; storing a copy preserves the valid combination state at this point.

Line 19 Critical

backtrack(cur, i + 1, target - candidates[i])

Recursively call backtracking with updated position and reduced target.

Recursing with the next index and decreased target explores all valid combinations including the chosen candidate, progressing the search.

Line 3 Core

candidates.sort()

Sort the candidates array in non-decreasing order.

Sorting groups duplicate candidates together, enabling the algorithm to skip duplicates efficiently during recursion and avoid generating duplicate combinations.

Line 10 Core

if target <= 0:

Check if the remaining target is less than or equal to zero.

This base case prunes paths where the sum exceeds the target, avoiding unnecessary recursion and improving efficiency.

Line 13 Core

prev = -1

Initialize a variable to track the previous candidate at this recursion depth.

Tracking the previous candidate enables skipping duplicates by comparing the current candidate to the previous one, preventing repeated combinations.

Line 21 Core

prev = candidates[i]

Update the previous candidate tracker to the current candidate.

Recording the current candidate as previous ensures duplicates are detected and skipped in subsequent iterations at this recursion depth.

Line 6 Core

def backtrack(cur, pos, target):

Define the recursive backtracking function with current combination, start position, and remaining target.

Encapsulating the recursive exploration in a helper function allows clean management of the current state and parameters needed to explore all valid combinations.

Line 9 Core

return

Return immediately after adding a valid combination.

Stopping recursion here prevents further exploration that would overshoot the target or generate invalid combinations.

Line 16 Core

continue

Continue to the next iteration if the candidate is a duplicate.

This enforces the pruning of duplicate branches, improving efficiency and correctness.

Line 18 Core

cur.append(candidates[i])

Add the current candidate to the current combination path.

Choosing the candidate extends the current combination, enabling exploration of deeper recursive states.

Line 23 Core

backtrack([], 0, target)

Start the backtracking process with an empty combination, starting index 0, and the full target.

This initial call triggers the recursive exploration of all valid combinations from the beginning of the sorted candidates list.

Line 11 Standard

return

Return immediately when the target is overshot or zero but handled above.

This prevents further exploration of invalid or completed paths, maintaining correctness and efficiency.

Line 14 Standard

for i in range(pos, len(candidates)):

Iterate over candidates starting from the current position.

This loop explores all possible next candidates to include in the current combination, enabling exhaustive search.

Line 4 Standard

res = []

Initialize an empty list to store the resulting unique combinations.

This list accumulates all valid combinations found during backtracking, serving as the final output container.

Line 24 Standard

return res

Return the list of all unique combinations found.

After recursion completes, this returns the accumulated valid combinations as the final solution.

Test Your Understanding

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

By sorting candidates and skipping over candidates that are the same as the previous candidate at the same recursion depth, the algorithm prevents exploring duplicate branches, ensuring each unique combination is generated only once.

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`

6	`def backtrack(cur, pos, target):`
7	`if target == 0:`
8	`res.append(cur.copy())`
9	`return`
10	`if target <= 0:`
11	`return`
13	`prev = -1`
14	`for i in range(pos, len(candidates)):`
15	`if candidates[i] == prev:`
16	`continue`
18	`cur.append(candidates[i])`
19	`backtrack(cur, i + 1, target - candidates[i])`
20	`cur.pop()`
21	`prev = candidates[i]`

Problem

Example

Approach

Solution

Step-by-Step Solution

Sort Candidates and Initialize Result Container

Explore Combinations Recursively with Duplicate Skipping

Initiate Backtracking and Return Final Results

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.