Subsets II

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 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

Tracing nums = [1,2,2] (already sorted): the root records [], then explores 1 before 2. 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:

• 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.