Subsets II

Medium#90subsets

You get a list of numbers, and some of them may repeat. Return every different subset: every group you can pick, from none of the numbers to all of them, with no group twice, even when equal numbers make it in another way. Our example: [3, 1, 3] has 6 such subsets: [ ], [1], [1, 3], [1, 3, 3], [3] and [3, 3].

90 Subsets IIWalkthrough · 1×

Example: every different subset of [3, 1, 3]. Watch the second 3: at the root it is skipped, since [3] is already there, but right after the first 3 it is allowed, and gives [3, 3].

[ ]11,31,3,333,3nums031123path—results—
not reached yeton the way herethis stepsaved subsetskipped: repeats the branch before itbefore start: out of reach

Find every different subset of [3, 1, 3]: 3 appears twice

01/32
restart · back · play · step
Speed
1function subsetsWithDup(nums):
2 sort(nums) // equal numbers side by side
3 path = []
4 results = []
5 grow(0)
6 return results
7
8function grow(start):
9 add copy of path to results
10 for i from start to len(nums) - 1:
11 if i > start and nums[i] == nums[i-1]: continue
12 path.add(nums[i])
13 grow(i + 1)
14 path.removeLast()
state
nums
[3, 1, 3]
start
–
i
–
path
–
results
–
click a step to go back

← → step · space play/pause

Why it works

  1. After sorting, equal numbers stand side by side, so a repeat is easy to see: it equals the number just before it.
  2. Within one call, a branch that starts with a repeat would build the same subsets as the branch of the first copy, so i > start with nums[i] == nums[i - 1] is skipped.
  3. At i == start the number follows the one just taken, not a sibling branch, so a second 3 after the first one is new: that is how [3, 3] and [1, 3, 3] appear exactly once.

Complexity

Time O(n × 2ⁿ): sorting is O(n log n), then at most 2ⁿ calls, each copying a path of up to n numbers. Memory O(n) besides the answer: the path and the call stack are at most n deep.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.