Bitmask Subset Enumeration
Iterate all subsets via integers.
Subsets as Numbers
Every subset of n items maps to a single integer. Count from 0 up, and each number's bits pick exactly which items are in. 🙂
How Many Subsets
A set of n items has 2^n subsets. So looping an integer from 0 to 2^n minus 1 visits every subset exactly once.
for mask in range(1 << n):
pass # mask is one subsetAll lessons in this course
- Brute Force Is a Valid Strategy
- Enumerate with itertools
- Bitmask Subset Enumeration
- Trim the Search Space Smartly