Subsets
Every subset falls out of n binary decisions: include element i or not. The recursion tree has exactly 2ⁿ leaves — one per subset.
- Category
- Backtracking
- Time complexity
- O(2ⁿ)
- Space complexity
- O(n)
Pseudocode
include element i, recurse exclude element i, recurse end of elements → emit subset 2ⁿ subsets total
Reference implementation
def subsets(i, path):
if i == n:
out.append(path); return
subsets(i+1, path + a[i])
subsets(i+1, path)