Input set size N (≤12). Visualize all 2^N bitmasks, submask iterations, and generate ready-to-paste C++ DP skeleton.
Subset DP is one loop and one line of bit arithmetic, and the line is s = (s - 1) & mask. It enumerates every submask of a mask in descending order without ever visiting one that is not a submask, and it is far from obvious why. The Bitmask Planner shows the output of that loop for any mask you click, alongside a table of every mask for a set of size N.
Two counters sit at the top and they are the numbers that decide whether your approach fits. The total mask count is 2 to the N. The total work of iterating submasks across every mask is 3 to the N, not 4 to the N, because each element is in the mask, in the submask, or in neither.
A C++ skeleton at the foot updates with your chosen N, complete with the __builtin_popcount call and the submask loop commented in place. Copy it and the button confirms with Got it! Copied 🚀.
Set N to 4 and click the row for mask 13, binary 1101. The panel lists 7 submasks in the order the loop produces them: 13, 12, 9, 8, 5, 4, 1. Note that 13 is included, since a mask is a submask of itself, and 0 is excluded, since the loop condition stops at zero. Seven is exactly 2 to the power of the popcount minus 1, and popcount of 13 is 3.
No proper submasks (mask = 0). Handle that case explicitly in your own code.Total masks
8
Submask iterations across all masks (3n)
27
All Bitmasks
Click a mask to see its submasks
| Mask | Binary | Set Bits | |S| |
|---|---|---|---|
| 0 | 000 | {} | 0 |
| 1 | 001 | {0} | 1 |
| 2 | 010 | {1} | 1 |
| 3 | 011 | {0, 1} | 2 |
| 4 | 100 | {2} | 1 |
| 5 | 101 | {0, 2} | 2 |
| 6 | 110 | {1, 2} | 2 |
| 7 | 111 | {0, 1, 2} | 3 |
C++ Bitmask DP Template
// Bitmask DP skeleton for N = 3
// Total masks: 8
#include <bits/stdc++.h>
using namespace std;
const int N = 3;
int dp[1 << N];
void solve() {
// Iterate over all masks
for (int mask = 0; mask < (1 << N); mask++) {
// __builtin_popcount(mask) = number of set bits
int bits = __builtin_popcount(mask);
// Submask iteration for mask = m
// for (int s = mask; s > 0; s = (s-1) & mask) { ... }
// Example: dp transition
dp[mask] = 0; // TODO: fill your logic
}
}
int main() {
int n; cin >> n;
solve();
}