Every subset is a number
Walk all subsets of a small list by counting from 0 to 2ⁿ − 1. About 10 minutes.
A subset is a row of yes/no
You are packing a bag and have 3 items. For each you answer yes or no, say yes, no, yes. Written as bits that is 101, a 3-bit number. Counting from 0 to 7 goes through every possible yes/no row exactly once, so it visits all 8 subsets.
To ask "is item i in?", shift the mask right by i and look at the last bit.
mask = 5 # 101 mask >> 0 & 1 # 1, item 0 is in mask >> 1 & 1 # 0, item 1 is out
- count
- 0
Count masks 0 to 7. Mask 0 takes nothing (sum 0); 1 takes item 0; 2 takes item 1.
2ⁿ grows fast
Each extra item doubles the number of subsets: 10 items give 1,024, 20 give about a million, and 30 give over a billion. That is why brute force over subsets only works when n is small, about 20 or less.
When a problem says n is at most 20 or so, that is the hint that looking at every subset is what is expected.
n = len(nums)
count = 0
for mask in range(1 << n):
total = 0
for i in range(n):
if mask >> i & 1:
total += nums[i]
if total == target:
count += 1
return countItems are [5, 7, 9]. Which items does mask 6 (binary 110) choose?
- A7 and 9
- B5 and 7
- CAll three
Show the answer
7 and 9. Bits 1 and 2 are set: items 1 and 2.
Subsets that hit a target
Count the subsets of nums (by position, including the empty subset) whose values add up to target.
nums = [1, 2, 3], target = 3 → 2
0 ≤ n ≤ 15 · −1,000 ≤ each value ≤ 1,000