Power Set
MediumTake it or leave it, at every element
Problem
Generate all subsets (the power set) of a set of distinct integers.
For each element, decide keep-or-skip — every combination of those choices is a subset.
The idea
For each element, branch twice: one path includes it and one excludes it. The 2^n leaves of that binary tree are exactly the subsets, which is why the power set has 2^n members.
The trick
- Add the current subset at the leaf, when every element has been decided.
- The bitmask version iterates 0..2^n-1 and reads the bits instead.
- O(2^n · n) to build and copy them all.
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].
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.