Subsets I
MediumTake or skip, collect the leaves
Problem
Return all possible subsets of an array of distinct integers.
Pick or skip each element to build every subset.
The idea
Walk the array deciding include or exclude for each element and record the accumulated subset once every element has been decided. With distinct inputs no deduplication is needed.
The trick
- 2^n subsets, so this is inherently exponential.
- Copy the working list when recording it — the same list is mutated as you backtrack.
Step 1 of 9. At each index, branch two ways: skip the element (left) or take it (right). The leaves are all subsequences of [1, 2].
1/9
Optimal
timeO(2ⁿ)spaceO(n)
Branch on each element.
1function go(i, path) {2 if (i === n) { emit(path); return; }3 go(i + 1, path); // don't take4 go(i + 1, [...path, a[i]]); // take5}Input
- nodes
- 7, 6 edges
Output
- output
- —
- count
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 2, 3]
- Output:
- [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
- Explanation:
- All 2^3 = 8 subsets.
Example 2
- Input:
- nums = [1, 2]
- Output:
- [[], [1], [2], [1, 2]]
- Explanation:
- 4 subsets including the empty set.
Example 3
- Input:
- nums = [0]
- Output:
- [[], [0]]
- Explanation:
- Just {} and {0}.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.