Here is solutions for Subsets II.

1. Understand the problem

• You are given an integer array nums that may contain duplicates.

• You must return all possible subsets (the power set) such that:

  • No duplicate subsets appear in the result.

  • Order of subsets does not matter.

  • Each subset is a list of integers.

2. Clarify constraints, asks 4 - 5 questions including edge cases.

1. Size of input?

• Typically 0 ≤ len(nums) ≤ 10.

1. Are duplicates allowed?

• Yes, this is the core difficulty.

1. Does order inside a subset matter?

• No, [1,2] is the same as [2,1], but we usually keep sorted order.

1. Can the input be empty?

• Yes → return [[]].

1. A negative numbers allowed?

• Yes, but it doesn’t affect the logic.

3. Explore examples.

1. Example 1:

Input:  [1,2,2]
Output: [[], [1], [2], [1,2], [2,2], [1,2,2]]

1. Example 2

Input:  [0]
Output: [[], [0]]

1. Example 3

Input:  [2,2]
Output: [[], [2], [2,2]]

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. Solution 1 — Naive (Generate All, Deduplicate with Set) - Time: O(2^n * n), Space: O(2^n)

• Idea:

  • Generate all subsets like normal Subsets I.

  • Sort each subset.

  • Store in a set to remove duplicates.

• Time: O(2^N * N)

• Space: O(2^N)

4.2. Solution 2 — Optimized Backtracking with Pruning (Correct Interview Solution ✅) - Time: O(2^N), Space: O(N)

• Key Idea:

  • Sort the array first so duplicates are adjacent.

• While backtracking:

  • If nums[i] == nums[i-1] and i > start, skip it.

  • This prevents duplicates at the same tree level.

  • ✅ This avoids duplicates during generation, not after.

• Time: O(2^N)

• Space: O(N)

5. Implement solutions.

5.1. Brute Force - Time: O(2^N * N), Space: O(2^N)

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = set()

        def backtrack(i, subset):
            if i == len(nums):
                res.add(tuple(subset))
                return

            subset.append(nums[i])
            backtrack(i + 1, subset)
            subset.pop()
            backtrack(i + 1, subset)

        nums.sort()
        backtrack(0, [])
        return [list(s) for s in res]

• Time: O(2^N * N)

• Space: O(2^N)

5.2. Backtracking - I - Time: O(2^N * N), Space: O(2^N)

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()

        def backtrack(i, subset):
            if i == len(nums):
                res.append(subset[::])
                return

            # Step 1: Pick nums[i]
            subset.append(nums[i])
            backtrack(i + 1, subset)
            subset.pop()

            # Step 2: Skip nums[i]
            while i + 1 < len(nums) and nums[i] == nums[i + 1]:
                i += 1
            backtrack(i + 1, subset)

        backtrack(0, [])
        return res

• Time: O(2^N * N)

• Space: O(2^N)

5.3. Backtracking - Pick like idea combination sum - II - Time: O(2^N * N), Space: O(N) extra space

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        def backtrack(i, subset):
            res.append(subset[::])

            for j in range(i, len(nums)):
                if j > i and nums[j] == nums[j - 1]:
                    continue
                subset.append(nums[j])
                backtrack(j + 1, subset)
                subset.pop()

        backtrack(0, [])
        return res

• Time: O(2^N * N)

• Space: O(2^N)

5.4. Iteration - Time: O(2^N * N), Space: O(1) extra space

• When a duplicate appears, only extend the subsets generated in the previous iteration to prevent duplicate subsets.

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = [[]]
        prev_Idx = idx = 0

        for i in range(len(nums)):
            idx = prev_idx if i >= 1 and nums[i] == nums[i - 1] else 0
            prev_idx = len(res)
            for j in range(idx, prev_idx):
                tmp = res[j].copy()
                tmp.append(nums[i])
                res.append(tmp)

        return res

• Time: O(2^N * N)

• Space: O(2^N)

6. Dry run testcases.

• nums = [1,1,2,3] => Auto skip the second 1 if duplicates with first 1.