Subsets II

Same shape as Subsets, but duplicate values in the input can otherwise produce duplicate subsets in the output (e.g. picking “the first 2” vs. “the second 2” from [2,2] both look like [2]).

Brute Force: Bitmask + Set Dedup

Time O(n · 2^n)Space O(n · 2^n)

Enumerate all 2^n bitmasks exactly as in Subsets, but since duplicate values now generate duplicate subsets, sort each candidate subset and only keep it if it hasn’t been seen before.

class Solution:
    def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        seen = set()
        result = []
        for mask in range(1 << n):
            subset = tuple(sorted(nums[i] for i in range(n) if mask & (1 << i)))
            if subset not in seen:
                seen.add(subset)
                result.append(list(subset))
        return result

Still visits all 2^n masks even though many collapse to the same subset once sorted — the dedup happens after the fact instead of being avoided.

Sort + Skip Adjacent Duplicates at Each Depth

OptimalTime O(n · 2^n)Space O(n)

Sort nums so equal values are adjacent, then reuse the Subsets backtracking template with one added rule: within a single call’s loop, skip a value if it equals the previous value at the same depth (i > start). The first occurrence of a repeated value is always explored fully; only its later duplicates at that same decision point are skipped, since they would just re-derive subsets already produced by the first occurrence.

class Solution:
    def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        result = []
        path = []

        def backtrack(start):
            result.append(path[:])
            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:
                    continue  # duplicate value at this depth, already covered
                path.append(nums[i])
                backtrack(i + 1)
                path.pop()

        backtrack(0)
        return result

The tree below plays the same trace on nums = [1,2,2]: each decision lights one subset, and the pruned duplicate SIBLINGS (struck through) are the ones the skip rule prevents — watch depth 1 twice. Inside the 1-branch we may still use both copies of 2 (they are at increasing depths, not siblings), but back at the root, the second top-level 2 is skipped as a sibling duplicate of the first:

path∅

loop122

Subset tree by depthrecorded 1

0[]

1···

2···

3·

1 / 8

current decisionrecorded subsetpruned duplicatenot reached yet

backtrack(0) records the empty set at the root, then its loop tries each value that can follow.

backtrack(0) → record []; loop i=0 (1) → path [1], record it
- backtrack(1) → loop i=1 (2) → path [1,2], record it
  - backtrack(2) → loop i=2 (2) → path [1,2,2], record it
- loop continues at i=2: nums[2]==nums[1] but i==start(1) is false only if i>start; here start=1, so i=2>1 and nums[2]==nums[1] → skip
back at root, loop i=1 (2) → path [2], record it
- backtrack(2) → path [2,2], record it
loop continues at i=2: i=2 > start(0) and nums[2]==nums[1] → skip (this is the top-level duplicate that would have produced [2] again)

Result: [[], [1], [1,2], [1,2,2], [2], [2,2]] — exactly 6, matching 2^3 minus the 2 duplicate subsets that the skip rule prevented from ever being generated.

Complexity: worst case (all distinct values) still explores all 2^n subsets, each copied in O(n) → O(n · 2^n) time; recursion depth and path are O(n) → O(n) auxiliary space, with no post-hoc dedup structure needed.

Brute Force: Bitmask + Set Dedup

Sort + Skip Adjacent Duplicates at Each Depth

More Backtracking practice