Subset Enumeration
Counting from 0 to 2^n - 1 enumerates every subset. sub = (sub - 1) & mask enumerates submasks.
Bitmask: Every subset of three
mask 0 = 000: the subset { }. All bits off is the empty set.
Cost
- Best
- O(2^n)
- Average
- O(2^n)
- Worst
- O(2^n)
- Space
- O(1)
Before this
Related
Taught by the same lesson
Bitmask covers these too, in the same run.