Bitmask Subset Enumeration
Iterate all subsets via integers.
Bitmask Subset Enumeration is a free Coding Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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 subset1 << n Is the Count
The shift 1 << n equals 2 to the power n. It is the clean, fast way to write the upper bound of your subset loop.
Read Bit i
To ask if item i is in the subset, test its bit with mask and 1 shifted left by i. A nonzero result means it is included.
if mask & (1 << i):
take(items[i])Build the Chosen List
Walk each bit position and collect the items whose bit is set. That turns one mask into the concrete subset it represents.
chosen = [items[i] for i in range(n) if mask & (1 << i)]Empty and Full Sets
Mask 0 is the empty subset, and the all-ones mask is the full set. Both come for free since your loop covers every value.
Sum Over a Subset
Inside the loop, add up the chosen items to score each subset. This is the heart of many small brute force solutions.
total = sum(v[i] for i in range(n) if mask & (1 << i))Count the Set Bits
The number of chosen items equals the popcount of the mask. In Python, bin(mask).count('1') gives it instantly.
size = bin(mask).count("1")Watch the Limit
Since there are 2^n subsets, this technique only fits small n. Around n equal to 20 is the practical ceiling for full enumeration.
Why Bitmasks Win
One integer loop replaces messy nested loops, and bit operations are fast. The code stays short, clear, and easy to test.
A Reusable Pattern
Loop the mask, decode its bits, score the subset, and track the best. Memorize this template and many subset problems become routine.
Quick Check
You want to test whether item i is included in the subset encoded by mask.
Recap
Loop a mask from 0 to 2^n minus 1, read bits with mask and 1 shifted left, and score each subset. It is clean brute force for small n. 🚀
Frequently asked questions
Is the “Bitmask Subset Enumeration” lesson free?
Yes — the full text of “Bitmask Subset Enumeration” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Bitmask Subset Enumeration”?
Iterate all subsets via integers. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Bitmask Subset Enumeration” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Brute Force Is a Valid Strategy
- Enumerate with itertools
- Bitmask Subset Enumeration
- Trim the Search Space Smartly