Print All Subsequences
MediumTake / don't take at each index
For each item, try both keeping it and skipping it, exploring every possible pick.
The idea
At every index make a binary choice: include the element or skip it, then recurse on the next index. The 2ⁿ leaves of this decision tree are all subsequences.
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.