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 use a set of sorted tuples to drop the duplicates.
from itertools import combinations
def subsetsWithDup(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 passes, but it wastes work: for input [2]*10 it materializes 1024 combinations to keep 11, and the hashing and copying overhead grows with every duplicate. The better approach never generates the duplicates in the first place.
Approach 2 — Backtracking with same-level duplicate skipping
Sort the array so equal values are adjacent. In the backtracking tree, a duplicate subset can only appear when two sibling branches at the same tree level (same start) begin with different copies of the same value, since both branches then enumerate identical completions. Allow the first occurrence at each level and continue past the rest: if i > start and nums[i] == nums[i-1]: skip. Backtracking here means building a partial subset depth-first and popping the last choice before trying the next.
def subsetsWithDup(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
The recursion tree for nums = [1,2,2], with the pruned duplicate branches shown dashed:
flowchart TD
A["path: [ ]"] -->|pick 1| B["[1]"]
A -->|"pick 2 (i=1)"| C["[2]"]
A -.->|"i=2: skip dup 2"| X["pruned"]
B -->|pick 2| D["[1,2]"]
B -.->|"i=2: skip dup 2"| Y["pruned"]
C -->|pick 2| E["[2,2]"]
D -->|pick 2| F["[1,2,2]"]
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
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.
def subsetsWithDup(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 just reintroduces Approach 1’s wasted work.
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.