Subsets

Medium#78subsets

You get a list of different numbers. Return every subset of it: every group you can pick, from none of the numbers to all of them, each group once, in any order. Our example: [2, 5, 8] has 2³ = 8 subsets, [ ] and [2] through [2, 5, 8].

78 SubsetsWalkthrough · 1×

Example: every subset of [2, 5, 8]. Watch the root move on to 5: from there only 8 can join, so [5, 2], the same as [2, 5], never comes up.

[ ]22,52,5,82,855,88nums021528path—results—
not reached yeton the way herethis stepsaved subsetout of reach (before start) or just removed

Find every subset of [2, 5, 8]

01/38
restart · back · play · step
Speed
1function subsets(nums):
2 path = []
3 results = []
4 grow(0)
5 return results
6
7function grow(start):
8 add copy of path to results // each call is one
9 for i from start to len(nums) - 1:
10 path.add(nums[i])
11 grow(i + 1) // only numbers after nums[i]
12 path.removeLast()
state
start
–
i
–
path
–
results
–
click a step to go back

← → step · space play/pause

Why it works

  1. Every call stands for one subset, the path that led to it, so saving at the start of each call saves every subset; the tree has exactly 2ⁿ calls.
  2. A call adds only numbers after the last one taken (start = i + 1). Each subset is then built in one order only, smallest index first, so none is saved twice.
  3. Removing the number after the call comes back leaves the path as it was before it, so the next number of the loop starts from the same subset.

Complexity

Time O(n × 2ⁿ): 2ⁿ calls, and each copies 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.