Subsets II — InterviewPrepKit

Solving tips

Same as Subsets but with duplicate values: sort first so equal values are adjacent, then apply the same-level skip rule.
Skip candidates[i] when i > start and nums[i] == nums[i-1]: this blocks starting two sibling branches with the same value while still allowing consecutive picks like [2,2].
Use i > start, not i > 0, or you wrongly suppress legitimate repeats where a child extends its parent with an equal value.
Time is O(n * 2^n), O(n) extra space; recording at every node captures subsets of all sizes, and no set-based dedup is needed.

Problem

You are given an integer array nums that may contain duplicate values. Return every possible subset of nums (the power set), but the result must not contain two subsets that are equal as multisets — e.g. [1,2] and [2,1] count as the same subset, and [2] may only appear once even if 2 appears twice in the input.

Subsets may be returned in any order, and the elements inside each subset may be in any order.

Examples

nums = [1,2,2] → [[], [1], [1,2], [1,2,2], [2], [2,2]] — the two 2s produce [2], [2,2], etc., but [2] is listed only once.
nums = [0] → [[], [0]] — a single element gives the empty set and itself.
nums = [4,4,4] → [[], [4], [4,4], [4,4,4]] — with all-equal elements, only subset sizes matter.

Constraints

1 <= nums.length <= 10 — output can hold up to 2^10 = 1024 subsets, so exponential enumeration is expected and fine.
-10 <= nums[i] <= 10

Think about it first

Hint 1

If there were no duplicates, this would be plain Subsets: at each index, either include the element or skip it. What goes wrong when two equal values exist? Which two different choice sequences build the same subset?

Hint 2

Sort the array first so equal values sit next to each other. Now duplicate subsets can only arise from choosing "the second 2 but not the first 2" versus "the first 2 but not the second 2".

Hint 3

In the backtracking loop over candidate positions `i` from `start`, skip `nums[i]` whenever `i > start` and `nums[i] == nums[i-1]`: within one level of the tree, never start a new branch with a value you already branched on at that level. That single `continue` removes all duplicates with no set-based dedup needed.

TL;DR

Sort, then backtrack and skip same-value siblings at each tree level — O(n · 2^n) time, O(n) extra space (beyond the output).

Approach 1 — Brute force: generate everything, dedup with a set

Generate all 2^n subsets exactly as in plain Subsets (or via itertools.combinations of every size), then throw the sorted tuples into a set to kill duplicates.

from itertools import combinations


class Solution:
    def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        seen: set[tuple[int, ...]] = set()
        res: list[list[int]] = []
        for k in range(len(nums) + 1):
            for combo in combinations(nums, k):
                if combo not in seen:
                    seen.add(combo)
                    res.append(list(combo))
        return res

Complexity: O(n · 2^n) time, O(n · 2^n) space for the dedup set.

With n <= 10 this actually passes, but it does blind work: for input [2]*10 it materializes 1024 combinations to keep 11, and the hashing/copying overhead grows with every duplicate. The lesson of this problem is to never generate the duplicates at all.

Approach 2 — Backtracking with same-level duplicate skipping

The insight: sort the array so equal values are adjacent. In the backtracking tree, a duplicate subset can only be produced when, at the same tree level (same start), we begin one branch with the first copy of a value and another branch with the second copy — both branches enumerate exactly the same completions. So allow the first occurrence at each level and continue past the rest: if i > start and nums[i] == nums[i-1]: skip. Backtracking is the classical technique of building a partial solution depth-first and undoing (popping) the last choice before trying the next one.

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

        def backtrack(start: int) -> None:
            res.append(path[:])          # every node of the tree is a subset
            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:
                    continue             # same value already branched at this level
                path.append(nums[i])
                backtrack(i + 1)
                path.pop()

        backtrack(0)
        return res

Walkthrough on nums = [1,2,2] (already sorted):

backtrack(0): record [].
i=0, push 1 → backtrack(1): record [1].
Inside, i=1, push 2 → backtrack(2): record [1,2]; then i=2, push 2 → record [1,2,2], pop back.
Back at start=1, i=2: i > start and nums[2] == nums[1] → skip (this branch would have rebuilt [1,2]). Pop the 1.
Top level i=1, push 2 → record [2]; inside i=2 (i == start, allowed), push 2 → record [2,2].
Top level i=2: duplicate at the same level → skip.

Result: [[], [1], [1,2], [1,2,2], [2], [2,2]] — six subsets, no dedup pass needed.

Complexity: O(n · 2^n) time (at most 2^n nodes, each copies a path of length ≤ n), O(n) recursion/path space beyond the output.

Approach 3 — Iterative cascading

The insight: plain Subsets can be built iteratively — for each number, append it to every subset built so far. With duplicates (after sorting), when the current number equals the previous one, append it only to the subsets created in the previous round; extending older subsets would recreate what the first copy already produced.

class Solution:
    def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        res: list[list[int]] = [[]]
        new_start = 0                    # index where the previous round's additions begin
        for i, x in enumerate(nums):
            start = new_start if i > 0 and x == nums[i - 1] else 0
            new_start = len(res)
            for j in range(start, new_start):
                res.append(res[j] + [x])
        return res

Walkthrough on [1,2,2]: start res = [[]]. Number 1: extend everything → [[], [1]], new items begin at index 1. Number 2 (not a dup of 1): extend everything → adds [2], [1,2]; new items begin at index 2. Number 2 (dup): extend only indices 2..3 → adds [2,2], [1,2,2]. Final: 6 subsets, same as Approach 2.

Complexity: O(n · 2^n) time, O(1) extra space beyond the output.

Common pitfalls

Forgetting to sort first — the nums[i] == nums[i-1] skip only works when equal values are adjacent.
Skipping with i > 0 instead of i > start — that also suppresses legitimate consecutive picks like [2,2]; the skip must apply only to siblings at the same level, not to a child extending its parent.
Appending path instead of path[:] — the same list object gets mutated later, corrupting every recorded subset.
Deduping at the end with a set of lists — lists aren’t hashable, and converting to tuples is Approach 1’s wasted work in disguise.

Pattern takeaway

When backtracking over a multiset, sort first, then enforce “first occurrence only” per tree level: at each choice point, never start two sibling branches with the same value (i > start and nums[i] == nums[i-1] → skip). This one guard converts any subsets/combinations/permutations enumerator into its duplicate-free variant without generating and filtering.