← DSA Atlas
Dedicated problem page · #90

Subsets II

MediumBacktrackingSubset enumeration with duplicate skippingDFS over a sorted array, recording every prefix path
Solve on LeetCode ↗
90
MediumBacktrackingDFS over a sorted array, recording every prefix pathSubset enumeration with duplicate skipping

Subsets II

Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets; the subsets may be returned in any order.

Open official problem prompt ↗
In plain English

List every distinct subset of a multiset exactly once.

Picture it like this

Choosing any assortment of toppings where two jars hold the same topping; a plate with 'one of that topping' is the same plate no matter which jar you scooped from, so you count it once.

Example
Input
nums = [1,2,2]
Output
[[],[1],[1,2],[1,2,2],[2],[2,2]]
Why
These are the six distinct subsets of the multiset {1,2,2}; picking either 2 alone yields the same subset [2], counted once.
Constraints
1 <= nums.length <= 10-10 <= nums[i] <= 10
Pattern lesson

See the pattern, then code

Subset enumeration with duplicate skipping
Recognition clue

You need the full power set but the input has duplicates, so you must suppress repeated subsets - sort and skip equal siblings at the same depth.

↗
Backtracking

Generate every valid combination, permutation, partition, or configuration.. Every node in the recursion tree is itself a valid subset, so record the path on entry. Sorting groups duplicates; skipping an equal value at the same level prevents generating the same subset via a different equal element.

New words, made simpleKnow these before the algorithm
Power set
The collection of all subsets, including the empty set and the full set.
Prefix subset
The current path at any recursion node, which is itself a valid subset.
Sibling skip
Skipping an equal value considered as an alternative at the same depth to avoid duplicate subsets.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
All subsets then dedupe

Works but explores duplicate branches and needs extra storage.

Generate 2^n subsets ignoring duplicates, then filter with a set of sorted tuples.

Time O(n * 2^n) plus hashingSpace O(2^n)
Best choiceSort + record path + skip equal siblings

Generates each distinct subset once with no filtering.

Append the path at each node; skip nums[i]==nums[i-1] when i>start; recurse from i+1.

Time O(n * 2^n)Space O(n)
The rule we keep true

Invariant

The path is always a strictly increasing-index selection of nums, and at any depth no two explored branches begin with the same value.

Why this is correct

Reasoning

Recursing from i+1 makes every subset correspond to a unique increasing index sequence. Because equal values are adjacent after sorting, skipping duplicates only at the same level (i>start) removes exactly the branches that would rebuild an identical subset while still allowing a value to appear deeper in the path.

The algorithm in three movesSay these aloud before coding
1Sort nums so duplicates are adjacent

sorted=[1,2,2]

2On entering each recursion, append a copy of the current path (it is a subset)

record [], then [1], then [1,2], then [1,2,2]

3Iterate candidates from start to end

later: skip the second 2 as a sibling

4Skip nums[i] equal to nums[i-1] when i > start to avoid duplicate subsets

5Choose nums[i], recurse from i+1, then pop

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
21
22
1 · Read[1,2,2]
2 · Askprepare
3 · Update statepath=[]
4 · Resultrecord []
Key takeaway

Sorted [1,2,2]; the highlighted 1,2 build the subset [1,2] on the path to [1,2,2].

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 2-4Sort and init

    Sorting makes duplicates adjacent so the sibling skip works.

  2. 2
    Lines 5-6Record subset

    Every recursion entry appends a copy of the path, capturing the empty set and all prefixes.

  3. 3
    Lines 7-9Skip duplicates

    i>start with nums[i]==nums[i-1] drops equal alternatives at the same depth.

  4. 4
    Lines 10-12Choose and undo

    Append, recurse from i+1 to move strictly forward, then pop to backtrack.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • All identical values, e.g. [2,2,2] -> subsets [],[2],[2,2],[2,2,2]
  • All distinct -> the full 2^n subsets
  • Single element -> [[],[x]]
!

Common beginner mistakes

  • Using i>0 instead of i>start, which incorrectly removes valid subsets containing repeated values
  • Recording the path by reference instead of a copy, so later mutation corrupts stored subsets
  • Recursing from i instead of i+1, which turns subsets into combinations-with-repetition
Check your understanding

Why is [] included and how is it produced?

More in Backtracking

#78SubsetsSubset enumeration by include/exclude#39Combination SumCombination search with unlimited reuse#46PermutationsPermutation generation#79Word SearchGrid path search with in-place visited marking#17Letter Combinations of a Phone NumberCartesian product of digit-letter groups#22Generate ParenthesesConstrained string construction