LeetCode 40: Combination Sum II Solution in Python Explained

Problem Statement

LeetCode 40, Combination Sum II, is a medium-level problem where you’re given an array of integers candidates (which may contain duplicates) and a target integer target. Your task is to return all unique combinations of numbers from candidates that sum up to target. Each number in candidates can be used only once in a combination, and the result must not contain duplicate combinations. Return the result as a list of lists.

Constraints

  • 1 <= candidates.length <= 100: Array length is between 1 and 100.
  • 1 <= candidates[i] <= 50: Each element is between 1 and 50.
  • 1 <= target <= 30: Target is between 1 and 30.

Example

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: [[1,1,6],[1,2,5],[1,7],[2,6]]
Explanation: These are unique combinations summing to 8.

Input: candidates = [2,5,2,1,2], target = 5
Output: [[1,2,2],[5]]
Explanation: Only these combinations sum to 5 without duplicates.

Input: candidates = [1,2], target = 4
Output: []
Explanation: No combination sums to 4.

Understanding the Problem

How do you solve LeetCode 40: Combination Sum II in Python? For candidates = [10,1,2,7,6,1,5] and target = 8, find unique combinations like [1,1,6], [1,2,5], [1,7], and [2,6]. Unlike LeetCode 39, each number can be used only once, and duplicates in candidates must be handled to avoid duplicate combinations. We’ll explore two approaches: a Backtracking Solution (optimal and primary) and an Alternative with Dynamic Programming (systematic but less practical here). The backtracking method sorts the array and skips duplicates efficiently.

Solution 1: Backtracking Approach (Primary)

Explanation

Sort candidates to handle duplicates easily, then use backtracking to build combinations. For each candidate, include it and recurse with the next index (no reuse), skipping duplicates at the same level to ensure uniqueness.

Here’s a flow for [1,1,2,5,6,7,10], target = 8 (sorted):

Try 1: [1], target = 7 -> [1,1], target = 6 -> [1,1,6], target = 0 (found)
Try 1: [1], target = 7 -> [1,2], target = 5 -> [1,2,5], target = 0 (found)
Try 1: [1], target = 7 -> [1,7], target = 0 (found)
Try 2: [2], target = 6 -> [2,6], target = 0 (found)
  1. Sort Candidates.
  • Enables duplicate skipping.
  1. Backtrack.
  • Try each candidate once, move to next index.
  1. Skip Duplicates.
  • Avoid same combinations at each level.
  1. Return Combinations.

Step-by-Step Example

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

We need [[1,1,6], [1,2,5], [1,7], [2,6]].

  • Goal: Find unique combinations summing to 8.
  • Result for Reference: [[1,1,6], [1,2,5], [1,7], [2,6]].
  • Start: Sort candidates = [1,1,2,5,6,7,10], target = 8, curr = [], result = [].
  • Step 1: i = 0, 1.
    • curr = [1], target = 7.
    • i = 1, 1, curr = [1,1], target = 6.
    • i = 4, 6, curr = [1,1,6], target = 0, add [1,1,6].
  • Step 2: Backtrack, i = 0, 1, curr = [1].
    • i = 2, 2, curr = [1,2], target = 5.
    • i = 3, 5, curr = [1,2,5], target = 0, add [1,2,5].
  • Step 3: Backtrack, i = 0, 1, curr = [1].
    • i = 5, 7, curr = [1,7], target = 0, add [1,7].
  • Step 4: i = 2, 2 (skip i=1 due to duplicate).
    • curr = [2], target = 6.
    • i = 4, 6, curr = [2,6], target = 0, add [2,6].
  • Finish: Return [[1,1,6], [1,2,5], [1,7], [2,6]].

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

We need [[1,2,2], [5]].

  • Start: Sort = [1,2,2,2,5].
  • Step 1: i = 0, 1, curr = [1], target = 4.
    • i = 1, 2, curr = [1,2], target = 2.
    • i = 2, 2, curr = [1,2,2], target = 0, add [1,2,2].
  • Step 2: i = 4, 5, curr = [5], target = 0, add [5].
  • Finish: Return [[1,2,2], [5]].

How the Code Works (Backtracking)

Here’s the Python code with line-by-line explanation:

def combinationSum2(candidates: list[int], target: int) -> list[list[int]]:
    # Line 1: Sort candidates to handle duplicates
    candidates.sort()
    result = []

    # Line 2: Backtracking helper
    def backtrack(start: int, target: int, curr: list[int]) -> None:
        # Line 3: Target reached
        if target == 0:
            result.append(curr[:])
            return
        # Line 4: Target overshot
        if target < 0:
            return

        # Line 5: Try candidates from start
        prev = -1  # Track previous used number
        for i in range(start, len(candidates)):
            # Line 6: Skip duplicates at same level
            if candidates[i] == prev:
                continue
            # Line 7: Add candidate
            curr.append(candidates[i])
            # Line 8: Recurse with next index (no reuse)
            backtrack(i + 1, target - candidates[i], curr)
            # Line 9: Backtrack
            curr.pop()
            prev = candidates[i]

    # Line 10: Start backtracking
    backtrack(0, target, [])
    # Line 11: Return result
    return result

Alternative: Dynamic Programming Approach

Explanation

Use DP to build combinations, accounting for single-use and duplicates. Store combinations for each sum, ensuring uniqueness by tracking used indices. Less efficient here due to duplicate handling.

  1. Initialize DP.
  2. Build Combinations.
  • Add candidates once per position.

3. Filter Duplicates. 4. Return dp[target].

Step-by-Step Example (Alternative)

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

  • Start: dp = [set() for _ in range(9)], dp[0] = {()}.
  • Step 1: cand = 1.
    • dp[1] = {(1,)}, dp[2] = {(1,1)}.
  • Step 2: cand = 2.
    • dp[3] = {(1,2)}, dp[4] = {(1,1,2)}.
  • Step 3: cand = 6, dp[8] = {(1,1,6), (2,6)}.
  • Step 4: cand = 7, dp[8] += {(1,7)}.
  • Finish: Convert to lists: [[1,1,6], [1,7], [2,6]].

How the Code Works (DP)

def combinationSum2DP(candidates: list[int], target: int) -> list[list[int]]:
    # Line 1: Sort and initialize DP with sets
    candidates.sort()
    dp = [set() for _ in range(target + 1)]
    dp[0].add(())

    # Line 2: Build combinations
    for cand in candidates:
        for t in range(target, cand - 1, -1):
            for combo in dp[t - cand]:
                dp[t].add(tuple(sorted(combo + (cand,))))

    # Line 3: Convert sets to list of lists
    return [list(combo) for combo in dp[target]]

Complexity

  • Backtracking:
    • Time: O(2^N) – N = len(candidates), exponential due to combinations.
    • Space: O(N) – Recursion stack.
  • Dynamic Programming:
    • Time: O(2^N * N) – Combinations plus sorting/processing.
    • Space: O(2^N) – Storing all unique combinations.

Efficiency Notes

Backtracking is more efficient and practical for LeetCode 40, pruning branches and handling duplicates naturally. DP is overkill and memory-intensive due to duplicate filtering.

Key Insights

Tips to master LeetCode 40:

  • Sort First: Simplifies duplicate skipping.
  • Single Use: Move to next index, no reuse.
  • Skip Duplicates: Check previous at each level.

Additional Example

For candidates = [1,2,2], target = 4:

  • Goal: [[1,2,2]].
  • Backtracking: [1,2,2], skip extra 2s at same level.
  • Result: [[1,2,2]].

Edge Cases

  • No Solution: [1,2], target = 4 – Return [].
  • All Duplicates: [2,2,2], target = 4 – Return [[2,2]].
  • Single Element: [5], target = 5 – Return [[5]].

Final Thoughts

The Backtracking solution is a gem for LeetCode 40 in Python—fast, intuitive, and perfect for unique combos. For a related challenge, try LeetCode 39: Combination Sum to compare with unlimited use! Ready to sum it up? Solve LeetCode 40 on LeetCode now and test it with [1,1,2,5] or targets like 6 or 8 to nail your backtracking skills. Dive in and conquer it!