Pattern visualizer

Subsets II

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. Animated on: nums = [1, 2, 2] contains a duplicate. Return every subset exactly once. Answer: [] [1] [1, 2] [1, 2, 2] [2] [2, 2]..

Sort, then skip a duplicate value among siblings

time O(n * 2^n)space O(n) recursion depth beyond the outputstep 1 / 10

[0]

[1]

[2]

line 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

Where to practice Backtracking

Practice Backtracking problems All Backtracking problems Back to roadmap