The problem
Same as Subsets, but the list may contain duplicates. Return all subsets without repeating the same subset twice.
Input: [1, 2, 2] Output: [[], [1], [1,2], [1,2,2], [2], [2,2]]
Picture it
Pizza toppings again, but two of them are the same kind. First sort them so identical toppings sit together. At each level we only branch on the first of a run of equal toppings; picking the second identical one at the same level would just recreate a pizza we already have.
How to recognise it
- It is the Subsets problem again, but the input may contain repeated values, and the answer must not contain the same subset twice.
- Two copies of the same number are interchangeable, so choosing "the first 2" or "the second 2" gives the same subset.
- The input is tiny (at most 10 numbers), so enumerating is allowed; the difficulty is avoiding duplicate answers, not speed.
- When duplicates cause duplicate results, think: sort first, then skip a value that equals the one just tried at the same level of choices.
Start with brute force
Generate all 2^n subsets as in the basic problem, sort each one so equal subsets look identical, and drop repeats with a set.
def subsets_with_dup_brute(nums):
n = len(nums)
seen = set()
for mask in range(1 << n):
pick = tuple(sorted(nums[i] for i in range(n) if mask >> i & 1))
seen.add(pick)
return [list(p) for p in seen]
It is correct. Time is O(n · 2^n) for the masks plus the sorting of each pick, and space is O(n · 2^n) for the set, even when most of those subsets are duplicates. With n = 10 that is 1,024 masks, which is fine; but the work and memory are spent on subsets that are then thrown away. For [2, 2, 2, 2, 2, 2, 2, 2, 2, 2] it builds 1,024 subsets to keep only 11.
From brute force to the idea
- Sort the numbers. Equal values now sit next to each other, so duplicates are easy to spot.
- Change the shape of the recursion. Instead of "take or leave position i", each call records its current
pickas a subset, then loopsfor i in range(start, len(nums)), addingnums[i]and recursing fromi + 1. Every call is itself an answer. - Find where duplicates come from. Within one loop, trying a second copy of a value as the next item builds the same subsets as trying the first copy did.
- Skip repeats at the same level.
if i > start and nums[i] == nums[i - 1]: continue. The first copy of a value is always allowed; a later copy at the same level is skipped. - Still allow deeper copies. In the recursive call,
starthas moved on, so the next copy is the first candidate there. That is how[2, 2]is produced.
This is the key idea: sort, then skip a value equal to its left neighbour unless it is the first choice at this level.
The key idea
Sort, then skip nums[i] when i > start and nums[i] == nums[i−1]. This removes duplicate branches.
Python solution
def subsets_with_dup(nums):
nums.sort(); res = []
def dfs(start, pick):
res.append(pick[:])
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue # same topping, same branch: skip
dfs(i + 1, pick + [nums[i]])
dfs(0, [])
return resIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force (all masks, then dedupe) | O(n · 2^n) | O(n · 2^n): even duplicates are stored until the set drops them |
| Sort and skip (shown code) | O(n log n) for the sort, then O(n · U) where U is the number of distinct subsets (at most 2^n) | O(n) beyond the output: recursion depth and pick |
Edge cases
- Empty list: returns
[[]]. - All equal (
[2, 2, 2]): returns[[], [2], [2, 2], [2, 2, 2]], four subsets, one per length. - No duplicates (
[1, 2, 3]): returns all 8 subsets, like the basic problem. - Unsorted input (
[2, 1, 2]): the code sorts it first and returns the same six subsets as[1, 2, 2]. - Input is changed:
nums.sort()sorts the caller's list in place. - Example (
[1, 2, 2]): returns[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]], six subsets rather than eight.
Common mistakes
- Skipping with
i > 0instead ofi > start. Then[1, 2, 2]returns only four subsets ([[], [1], [1, 2], [2]]) because[2, 2]and[1, 2, 2]are wrongly skipped. - Forgetting to sort. For
[2, 1, 2]equal values are not neighbours, and[2]appears twice. - Removing duplicates after the fact with
seton lists. Lists are not hashable, so you must convert each to a tuple, and the work was already wasted.
Without generating them, count the distinct subsets of a list that may contain duplicates. For [1, 2, 2] the answer is 6. Describe your approach, then write it if you like.
Compare with our answer
A distinct subset is decided by how many copies of each distinct value it takes. A value that appears c times can be taken 0, 1, ..., c times, which is c + 1 options, and the choices for different values are independent. Multiply them.
from collections import Counter
from math import prod
def count_distinct_subsets(nums):
return prod(c + 1 for c in Counter(nums).values())
For [1, 2, 2] this is (1 + 1) × (2 + 1) = 6, and for [2, 2, 2] it is 4. Time O(n), space O(k) for k distinct values. The empty list gives 1, the empty subset.
A strong answer mentions: counting copies per value, c + 1 choices each, multiplying because the choices are independent, and why this beats generating every subset.
1. Given up to 10 tiles, some with the same letter, you must list every distinct selection of tiles (letters only, order irrelevant). Which approach fits best?
Sorting makes equal letters adjacent, so skipping a repeated letter at the same level avoids duplicate selections before they are built. Permutations include order, masks create duplicates that must be thrown away later, and greedy returns only one answer.
2. Why does the check use i > start and not i > 0?
The skip only applies to repeats within the same loop. With i > 0, a 2 right after a 2 chosen one level up would be skipped too, so [2, 2] would never be built.
3. A learner changes i > start to i > 0. How many subsets does the code return for [1, 2, 2], where six is correct?
The change returns [[], [1], [1, 2], [2]]: a second 2 is skipped even when its first copy was chosen on the level above. The other counts do not happen on this input.
Score 60% or more and the lesson is marked complete.