DSA Tracker

Visualize

Subsets II

Sort, then skip a duplicate value among siblings

time O(n * 2^n)space O(n) recursion depth beyond the output

The plain Subsets recursion builds each subset by choosing a next index from start onward, so no subset is ever built in two different orders. Duplicates therefore arise from just one place: two equal VALUES at different indices offered as alternatives at the same depth. Sort the array so equal values are adjacent, then inside the loop refuse nums[i] when it equals nums[i - 1] and i > start. The i > start part is the subtle half — the same value one level deeper (chosen right after its twin) is a genuinely new subset, and the guard must let it through. The cells row is the sorted input: tinted cells are the current path, and a red cell is a duplicate being skipped.

Details

Animated on: nums = [1, 2, 2] contains a duplicate. Return every subset exactly once. Answer: [] [1] [1, 2] [1, 2, 2] [2] [2, 2].

Problem:Subsets IIMedium

Pattern:Backtracking Basics

Sort, then skip a duplicate value among siblings

step 1 / 10

1
[0]
2
[1]
2
[2]

Sort first: nums <- [1, 2, 2]. Equal values are now neighbours, so "is this the same value as the one I just tried at this depth?" becomes a single comparison with nums[i - 1]. Without sorting, the duplicates could sit anywhere and picking them in a different order would still build the same subset twice.

Pseudocode
1FUNCTION subsetsWithDup(nums)
2  SORT nums
3  out <- EMPTY LIST, path <- EMPTY LIST
4  FUNCTION backtrack(start)
5    APPEND COPY(path) TO out
6    FOR i <- start TO LENGTH(nums) - 1
7      IF i > start AND nums[i] = nums[i - 1]
8        CONTINUE
9      APPEND nums[i] TO path
10      backtrack(i + 1)
11      REMOVE LAST FROM path
12  backtrack(0)
13  RETURN out

← / → step · space play · Home restart

Every step in words

Show all 10 steps
  1. Sort first: nums <- [1, 2, 2]. Equal values are now neighbours, so "is this the same value as the one I just tried at this depth?" becomes a single comparison with nums[i - 1]. Without sorting, the duplicates could sit anywhere and picking them in a different order would still build the same subset twice.
  2. Every path is a subset, so record [] the moment this call begins — there is no "leaf" test. 1 subset so far. Next choices come from index 0 onward, never earlier, so each subset is built in one fixed order.
  3. Every path is a subset, so record [1] the moment this call begins — there is no "leaf" test. 2 subsets so far. Next choices come from index 1 onward, never earlier, so each subset is built in one fixed order.
  4. Every path is a subset, so record [1, 2] the moment this call begins — there is no "leaf" test. 3 subsets so far. Next choices come from index 2 onward, never earlier, so each subset is built in one fixed order.
  5. Every path is a subset, so record [1, 2, 2] the moment this call begins — there is no "leaf" test. 4 subsets so far. Next choices come from index 3 onward, never earlier, so each subset is built in one fixed order.
  6. Skip: nums[2]=2 equals nums[1]=2, and i=2 > start=1 means this is a SIBLING choice at the same depth — the 2 branch already produced every subset that begins [1, 2]. Taking it again would duplicate them. Note the guard needs i > start: a duplicate one level DEEPER is legal, which is how [1, 2, 2] still gets built.
  7. Every path is a subset, so record [2] the moment this call begins — there is no "leaf" test. 5 subsets so far. Next choices come from index 2 onward, never earlier, so each subset is built in one fixed order.
  8. Every path is a subset, so record [2, 2] the moment this call begins — there is no "leaf" test. 6 subsets so far. Next choices come from index 3 onward, never earlier, so each subset is built in one fixed order.
  9. Skip: nums[2]=2 equals nums[1]=2, and i=2 > start=0 means this is a SIBLING choice at the same depth — the 2 branch already produced every subset that begins [2]. Taking it again would duplicate them. Note the guard needs i > start: a duplicate one level DEEPER is legal, which is how [2, 2] still gets built.
  10. Loop exhausted at every level, so the recursion unwinds to the top. 6 unique subsets: [] [1] [1, 2] [1, 2, 2] [2] [2, 2]. The plain power set of 3 elements has 8; the 2 skipped sibling branches would have rebuilt [1, 2] and [2] a second time.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Subsets II in the editorAll Backtracking problemsBack to roadmap