Lesson

13.6Combination Sum II

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 Inputs

Example 1:

Example 2:

Problem Solution

Approach

To find all unique combinations that sum up to the target where each number can be used only once, we can use a recursive backtracking approach with the following strategies:

Sort the Array: Sorting helps in identifying and skipping duplicates easily.
Backtracking with Choices: At each step, decide whether to include the current element in the combination or skip it.
Skip Duplicates: To avoid duplicate combinations, skip over elements that are the same as the previous one during the same recursion depth.

Steps

Sort the Array:
- Begin by sorting the candidates array. Sorting helps in easily skipping duplicates and optimizing the backtracking process.
Initialize:
- Create an empty list ans to store all valid combinations.
- Create an empty list current to store the current combination being explored.
Recursive Backtracking Function (backtrack):
- Parameters:
  - start (current index in candidates),
  - target (remaining sum),
  - current (current combination).
- Base Case:
  - If target is 0, it means the current combination sums up to the original target. Add a copy of current to ans.
  - If target becomes negative, stop exploring this path as it cannot lead to a valid combination.
- Recursive Case:
  - Iterate through the candidates starting from the start index.
  - For each candidate:
    - Skip Duplicates: If the current candidate is the same as the previous one and it's not the first candidate in this recursion depth, skip it to avoid duplicate combinations.
    - Include the Candidate:
      - Add the candidate to current.
      - Recursively call backtrack with updated target (target - candidate) and the next index (i + 1) since each number can be used only once.
      - Remove the last candidate from current to backtrack and explore other possibilities.
Start Backtracking:
- Call the backtrack function starting from index 0 with the original target and an empty current combination.
Return the Result:
- After exploring all possibilities, return the ans list containing all valid combinations.

Time & Space Complexity

Time Complexity:
- O(2^n), where n is the number of candidates. In the worst case, the algorithm explores all possible subsets.
Space Complexity:
- O(n), where n is the number of candidates. This space is used by the recursion stack and the current combination list.

Code Snippet

Dry Run

Let's perform a dry run with candidates = [10,1,2,7,6,1,5] and target = 8.

Sort the Array:
- candidates = [1,1,2,5,6,7,10]
Initial Call: backtrack(0, 8)
- current = []
First Level (start = 0, target = 8):
- i = 0: Candidate = 1
  - Include 1: current = [1]
  - Recurse: backtrack(1, 7)
Second Level (start = 1, target = 7):
- i = 1: Candidate = 1
  - Include 1: current = [1,1]
  - Recurse: backtrack(2, 6)
Third Level (start = 2, target = 6):
- i = 2: Candidate = 2
  - Include 2: current = [1,1,2]
  - Recurse: backtrack(3, 4)
Fourth Level (start = 3, target = 4):
- i = 3: Candidate = 5
  - 5 > 4, break the loop.
  - Backtrack to current = [1,1,2]
Back to Third Level (start = 2, target = 6):
- i = 3: Candidate = 5
  - Include 5: current = [1,1,5]
  - Recurse: backtrack(4, 1)
Fifth Level (start = 4, target = 1):
- i = 4: Candidate = 6
  - 6 > 1, break the loop.
  - Backtrack to current = [1,1,5]
Back to Third Level (start = 2, target = 6):
- i = 4: Candidate = 6
  - Include 6: current = [1,1,6]
  - Recurse: backtrack(5, 0)
Sixth Level (start = 5, target = 0):
- target === 0, add [1,1,6] to ans
- Backtrack to current = [1,1]
Back to Second Level (start = 1, target = 7):
- i = 2: Candidate = 2
  - Include 2: current = [1,1,2]
  - Recurse: backtrack(3, 5)
Third Level (start = 3, target = 5):
- i = 3: Candidate = 5
  - Include 5: current = [1,1,2,5]
  - Recurse: backtrack(4, 0)
Seventh Level (start = 4, target = 0):
- target === 0, add [1,1,2,5] to ans
- Backtrack to current = [1,1,2]
Back to Third Level (start = 3, target = 5):
- i = 4: Candidate = 6
  - 6 > 5, break the loop.
  - Backtrack to current = [1,1,2]
Back to Second Level (start = 1, target = 7):
- i = 3: Candidate = 5
  - Include 5: current = [1,1,5]
  - Recurse: backtrack(4, 2)
Third Level (start = 4, target = 2):
- i = 4: Candidate = 6
  - 6 > 2, break the loop.
  - Backtrack to current = [1,1,5]
Back to Second Level (start = 1, target = 7):
- i = 4: Candidate = 6
  - Include 6: current = [1,1,6]
  - Recurse: backtrack(5, 1)
Fourth Level (start = 5, target = 1):
- i = 5: Candidate = 7
  - 7 > 1, break the loop.
  - Backtrack to current = [1,1,6]
Back to Second Level (start = 1, target = 7):
- i = 5: Candidate = 7
  - Include 7: current = [1,1,7]
  - Recurse: backtrack(6, 0)
Eighth Level (start = 6, target = 0):
- target === 0, add [1,1,7] to ans
- Backtrack to current = [1,1]
Back to Second Level (start = 1, target = 7):
- i = 6: Candidate = 10
  - 10 > 7, break the loop.
  - Backtrack to current = [1,1]
Back to First Level (start = 0, target = 8):
- i = 1: Candidate = 1 (Duplicate of previous, skip)
- i = 2: Candidate = 2
  - Include 2: current = [1,2]
  - Recurse: backtrack(3, 6)
Second Level (start = 3, target = 6):
- i = 3: Candidate = 5
  - Include 5: current = [1,2,5]
  - Recurse: backtrack(4, 1)
Third Level (start = 4, target = 1):
- i = 4: Candidate = 6
  - 6 > 1, break the loop.
  - Backtrack to current = [1,2,5]
Back to Second Level (start = 3, target = 6):
- i = 4: Candidate = 6
  - Include 6: current = [1,2,6]
  - Recurse: backtrack(5, 0)
Fourth Level (start = 5, target = 0):
- target === 0, add [1,2,6] to ans
- Backtrack to current = [1,2]
Back to Second Level (start = 3, target = 6):
- i = 5: Candidate = 7
  - 7 > 6, break the loop.
  - Backtrack to current = [1,2]
Back to First Level (start = 0, target = 8):
- i = 3: Candidate = 5
  - Include 5: current = [1,5]
  - Recurse: backtrack(4, 3)
Second Level (start = 4, target = 3):
- i = 4: Candidate = 6
  - 6 > 3, break the loop.
  - Backtrack to current = [1,5]
Back to First Level (start = 0, target = 8):
- i = 4: Candidate = 6
  - Include 6: current = [1,6]
  - Recurse: backtrack(5, 2)
Second Level (start = 5, target = 2):
- i = 5: Candidate = 7
  - 7 > 2, break the loop.
  - Backtrack to current = [1,6]
Back to First Level (start = 0, target = 8):
- i = 5: Candidate = 7
  - Include 7: current = [1,7]
  - Recurse: backtrack(6, 1)
Third Level (start = 6, target = 1):
- i = 6: Candidate = 10
  - 10 > 1, break the loop.
  - Backtrack to current = [1,7]
Back to First Level (start = 0, target = 8):
- i = 6: Candidate = 10
  - 10 > 8, break the loop.
  - Backtrack to current = []
Final Result: [[1,1,6], [1,2,5], [1,7], [2,6]]

Complexity Analysis

Optimized Time and Space

The recursive backtracking approach explores all possible combinations by making a binary choice at each step: include the current candidate or exclude it.

Time Complexity:
- O(2^n), where n is the number of candidates. This is because each candidate can either be included or excluded, leading to 2^n possible combinations in the worst case.
Space Complexity:
- O(n), where n is the number of candidates. This space is used by the recursion stack and the current combination list.

Optimizations:

Sorting and Skipping Duplicates: Sorting the array allows us to skip over duplicate elements easily, reducing the number of recursive calls and avoiding duplicate combinations.
Early Termination: By breaking the loop when the current candidate exceeds the remaining target, we prevent unnecessary exploration of further candidates.

Conclusion

The Combination Sum II problem is a classic example of using recursive backtracking to explore all unique combinations that meet a specific criterion—in this case, summing up to a target value with each number used only once. By sorting the input array and carefully managing choices to include or exclude each candidate, we can efficiently generate all valid combinations while avoiding duplicates.

Understanding this approach not only helps in solving similar combinatorial problems but also reinforces fundamental concepts in recursion, backtracking, and algorithm optimization. Implementing the solution in a functional style without using classes makes the code more concise and easier to understand, especially for beginners. By systematically breaking down the problem and applying strategic decision-making, complex problems become manageable and solvable with clarity and confidence.

Previous Next