#40

Medium

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Combination Sum II

Find all unique combinations of numbers that sum to a target using backtracking with careful pruning to avoid duplicates.

array backtracking

Problem Statement

Given a list of candidate integers and a target integer, determine all unique combinations of candidates where the sum equals the target. Each number in the list can only be used once in a combination, so careful tracking of used elements is essential to avoid duplicate results.

Your solution must return all unique combinations without repetition. Efficient pruning during backtracking is necessary because exploring all subsets without eliminating duplicates can lead to exponential time waste, especially with repeated candidate values.

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 details omitted.

Example 2

Input: candidates = [2,5,2,1,2], target = 5

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

Example details omitted.

Constraints

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

Solution Approach

Sort and Prepare Candidates

Start by sorting the candidate array. Sorting helps in pruning duplicate values and allows early stopping when the current sum exceeds the target. This setup ensures the backtracking search explores only valid paths.

Backtracking with Pruning

Use a recursive backtracking function to build combinations. Skip candidates that are identical to the previous one at the same recursion depth to prevent duplicate combinations. Stop recursion if the running sum exceeds the target to prune unnecessary paths.

Collect Valid Combinations

Whenever the running sum matches the target, add a copy of the current path to the results. After exploring each candidate, backtrack by removing the last element to explore alternative paths, ensuring all unique solutions are captured.

Complexity Analysis

Metric	Value
Time	O(2^N)
Space	O(N)

Time complexity is O(2^N) due to exploring subsets of candidates, and space complexity is O(N) for the recursion stack and temporary combination path storage.

What Interviewers Usually Probe

Check if candidates are sorted to simplify duplicate handling.
Ask about pruning early when sum exceeds target.
Probe understanding of skipping duplicates in backtracking to avoid repeated combinations.

Common Pitfalls or Variants

Common pitfalls

Not sorting candidates first, which complicates duplicate skipping.
Using a candidate multiple times per combination when only single use is allowed.
Failing to prune recursion early, leading to excessive computation and timeouts.

Follow-up variants

Combination Sum (allowing unlimited usage of candidates).
Target Sum with negative numbers included, requiring careful pruning.
Finding combinations of a fixed length that sum to the target.

FAQ

What is the main difference between Combination Sum and Combination Sum II?

Combination Sum II allows each candidate to be used only once, whereas Combination Sum permits unlimited use of each candidate.

How does backtracking with pruning work in Combination Sum II?

It recursively explores candidate combinations, skipping duplicates and stopping paths where the current sum exceeds the target to optimize search.

Why do we need to sort candidates first?

Sorting ensures duplicates are adjacent, which allows easy skipping of repeated elements and enables early pruning when the sum exceeds the target.

Can the solution handle candidates with multiple duplicates?

Yes, but careful skipping of repeated values during the same recursion depth is necessary to prevent duplicate combinations in the results.

What is the time complexity of solving Combination Sum II?

The worst-case time complexity is O(2^N), as all subsets of candidates may need to be explored, though pruning reduces practical computation significantly.

terminal

Solution

Solution 1: Sorting + Pruning + Backtracking

We can first sort the array to facilitate pruning and skipping duplicate numbers.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(i: int, s: int):
            if s == 0:
                ans.append(t[:])
                return
            if i >= len(candidates) or s < candidates[i]:
                return
            for j in range(i, len(candidates)):
                if j > i and candidates[j] == candidates[j - 1]:
                    continue
                t.append(candidates[j])
                dfs(j + 1, s - candidates[j])
                t.pop()

        candidates.sort()
        ans = []
        t = []
        dfs(0, target)
        return ans

Solution 2: Sorting + Pruning + Backtracking(Another Form)

We can also change the implementation logic of the function $dfs(i, s)$ to another form. If we choose the current number, we add the current number to the search path $t$, then recursively call the function $dfs(i + 1, s - candidates[i])$, and after the recursion ends, we remove the current number from the search path $t$. If we do not choose the current number, we can skip all numbers that are the same as the current number, then recursively call the function $dfs(j, s)$, where $j$ is the index of the first number that is different from the current number.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(i: int, s: int):
            if s == 0:
                ans.append(t[:])
                return
            if i >= len(candidates) or s < candidates[i]:
                return
            for j in range(i, len(candidates)):
                if j > i and candidates[j] == candidates[j - 1]:
                    continue
                t.append(candidates[j])
                dfs(j + 1, s - candidates[j])
                t.pop()

        candidates.sort()
        ans = []
        t = []
        dfs(0, target)
        return ans

Continue Practicing

#39 combination sum #37 sudoku solver #46 permutations