LeetCode 90: Subsets II Solution in Python Explained

Problem Statement

In LeetCode 90, you’re given an integer array nums that may contain duplicates. Your task is to return all possible unique subsets (the power set), excluding duplicate subsets, in any order. This builds on LeetCode 78: Subsets, adding the twist of duplicates, and differs from sequence generation like LeetCode 89: Gray Code.

Constraints

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

Example

Let’s see some cases:

Copy codeInput: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Explanation: All unique subsets, no duplicates like [2,2] repeated.

Copy codeInput: nums = [0]
Output: [[],[0]]
Explanation: Subsets of a single element.

Copy codeInput: nums = [1,1,1]
Output: [[],[1],[1,1],[1,1,1]]
Explanation: Unique subsets with duplicates handled.

These examples show we’re generating unique subsets despite duplicates.

Understanding the Problem

How do you solve LeetCode 90: Subsets II in Python? Take nums = [1,2,2]. We need all unique subsets: [[],[1],[1,2],[1,2,2],[2],[2,2]]. Duplicates (e.g., two [2]) must be avoided. This isn’t an array merge like LeetCode 88: Merge Sorted Array; it’s about combinatorial generation. We’ll use: 1. Iterative Backtracking: O(2ⁿ) time, O(n) space—our top pick. 2. Recursive Backtracking: O(2ⁿ) time, O(n) space—a traditional approach.

Let’s dive into the primary solution.

Solution 1: Iterative Backtracking Approach (Primary)

Explanation

Sort the array to group duplicates, then iteratively build subsets by adding each number to existing subsets, skipping duplicates by checking the previous number. This ensures uniqueness without extra checks.

For nums = [1,2,2]:

• Start: [[]].
• Add 1: [[],[1]].
• Add 2: [[],[1],[2],[1,2]].
• Add 2 (skip duplicate for existing): [[],[1],[2],[1,2],[2,2],[1,2,2]].

Step-by-Step Example

Example 1: nums = [1,2,2]

Goal: Return [[],[1],[1,2],[1,2,2],[2],[2,2]].

• Start: Sort nums = [1,2,2], result = [[]].
• Step 1: num = 1 (i=0).
• New subsets: [1].
• result = [[],[1]].
• Step 2: num = 2 (i=1).
• New subsets: [2], [1,2].
• result = [[],[1],[2],[1,2]].
• Step 3: num = 2 (i=2, prev 2).
• Start from len=4: Add [2,2], [1,2,2].
• result = [[],[1],[2],[1,2],[2,2],[1,2,2]].
• Finish: Return [[],[1],[2],[1,2],[2,2],[1,2,2]].

Example 2: nums = [0]

Goal: Return [[],[0]].

• Start: result = [[]].
• Step 1: num = 0.
• New subsets: [0].
• result = [[],[0]].
• Finish: Return [[],[0]].

Example 3: nums = [1,1,1]

Goal: Return [[],[1],[1,1],[1,1,1]].

• Start: Sort nums = [1,1,1], result = [[]].
• Step 1: num = 1.
• [[],[1]].
• Step 2: num = 1.
• Start from len=2: [1,1].
• [[],[1],[1,1]].
• Step 3: num = 1.
• Start from len=3: [1,1,1].
• [[],[1],[1,1],[1,1,1]].
• Finish: Return [[],[1],[1,1],[1,1,1]].

How the Code Works (Iterative Backtracking) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef subsetsWithDup(nums: list[int]) -> list[list[int]]:
    # Line 1: Sort the input array
    nums.sort()
    # Sorts nums in ascending order (e.g., [1,2,2] stays [1,2,2], [2,1,2] becomes [1,2,2])
    # Ensures duplicates are adjacent, simplifying duplicate handling

    # Line 2: Initialize result with the empty subset
    result = [[]]
    # Starts with [[]], the base case of the power set (empty subset)
    # Will grow by adding elements iteratively

    # Line 3: Iterate over each number in nums
    for i in range(len(nums)):
        # i goes from 0 to len(nums)-1 (e.g., 0 to 2 for [1,2,2])
        # Each iteration processes one number

        # Line 4: Determine start index for adding new subsets
        start = 0 if i == 0 or nums[i] != nums[i-1] else len(result)
        # If i=0 (first element) or current number differs from previous (no duplicate),
        # start = 0: add to all existing subsets
        # If duplicate (e.g., second 2), start = len(result): only add to subsets from previous iteration
        # e.g., for i=2, nums[2]=2, nums[1]=2, start = 4 (len([[], [1], [2], [1,2]]))

        # Line 5: Get current length of result
        curr_len = len(result)
        # Stores the number of subsets before adding new ones (e.g., 2 for [[], [1]])
        # Used to iterate over existing subsets to duplicate

        # Line 6: Generate new subsets
        for j in range(start, curr_len):
            # j iterates from start to curr_len-1 (e.g., 0 to 1 initially, 4 to 5 for duplicate 2)
            # Selects which subsets to extend with the current number

            # Line 7: Create new subset by extending existing one
            new_subset = result[j] + [nums[i]]
            # Takes subset at j and appends current number
            # e.g., j=0, result[0]=[], nums[0]=1 -> [1]; j=4, result[4]=[2], nums[2]=2 -> [2,2]

            # Line 8: Append new subset to result
            result.append(new_subset)
            # Adds the new subset to the result list
            # e.g., result becomes [[], [1]] after first append, later [[], [1], [2], [1,2], [2,2], [1,2,2]]

    # Line 9: Return the complete list of unique subsets
    return result
    # Returns all unique subsets (e.g., [[], [1], [2], [1,2], [2,2], [1,2,2]] for [1,2,2])
    # Total length is ≤ 2^n due to duplicates

This detailed explanation ensures the iterative process is clear, handling duplicates efficiently.

Alternative: Recursive Backtracking Approach

Explanation

Recursively build subsets by choosing to include or exclude each number, sorting first and skipping duplicates by tracking the previous choice. Uses a helper function to explore all paths.

For [1,2,2]:

• Start: [].
• Add 1 or skip: [], [1].
• Add 2 or skip: [], [2], [1], [1,2].
• Add 2 or skip (skip if prev 2 taken): [2,2], [1,2,2].

Step-by-Step Example (Alternative)

For [1,2,2]:

• Depth 0: [].
• Depth 1: [], [1].
• Depth 2: [], [2], [1], [1,2].
• Depth 3: [2,2], [1,2,2].
• Finish: [[],[1],[2],[1,2],[2,2],[1,2,2]].

How the Code Works (Recursive)

Copy codedef subsetsWithDupRecursive(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []
    def backtrack(start: int, curr: list[int]):
        result.append(curr[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue
            curr.append(nums[i])
            backtrack(i + 1, curr)
            curr.pop()
    backtrack(0, [])
    return result

Complexity

• Iterative Backtracking:
• Time: O(2ⁿ) – generates all subsets.
• Space: O(n) – temporary subset storage.
• Recursive Backtracking:
• Time: O(2ⁿ) – explores all combinations.
• Space: O(n) – recursion stack.

Efficiency Notes

Both are O(2ⁿ) time (power set size), but Iterative is more space-efficient and easier to follow, making it the preferred choice—Recursive offers a classic backtracking perspective.

Key Insights

• Sorting: Groups duplicates.
• Duplicate Skip: Ensures uniqueness.
• Power Set: All possible combinations.

Additional Example

For nums = [4,4,4,1,4]:

• Goal: [[],[1],[1,4],[1,4,4],[1,4,4,4],[4],[4,4],[4,4,4],[4,4,4,4]].
• Iterative: Builds step-by-step, skipping duplicate additions.

Edge Cases

• Single Element: [1] → [[],[1]].
• All Duplicates: [1,1] → [[],[1],[1,1]].
• Empty: Not applicable (constraint n ≥ 1).

Both solutions handle these well.

Final Thoughts

LeetCode 90: Subsets II in Python is a fun combinatorial challenge. The Iterative Backtracking solution is practical and clear, while Recursive Backtracking offers a traditional approach. Want more? Try LeetCode 78: Subsets for the no-duplicates version or LeetCode 89: Gray Code for binary fun. Ready to practice? Solve LeetCode 90 on LeetCode with [1,2,2], aiming for [[],[1],[1,2],[1,2,2],[2],[2,2]]—test your skills now!