mask ranges over [0,2^n); bit i denotes item i; sub=(sub-1)&mask enumerates nonempty submasks.
Recognition signals
n is small and every subset matters
Choice state is a Boolean set
Fast union/intersection/difference is useful
Inclusion-exclusion enumerates property subsets
All subsets of one fixed set are needed
False friends
Signal
Why it is different
Large n
2^n becomes infeasible quickly; seek pruning or a different state dimension.
High multiplicities per item
One bit expresses presence, not a count.
Core invariant
Every mask corresponds to exactly one chosen set, and bit operations faithfully implement set operations.
State, transition, and processing order
Item
Definition
State
Current mask, item list, optional submask, and full-mask boundary.
Transition
Increment mask for all sets; update a submask with (sub-1)&mask.
Frontier / order
Numeric order is an encoding frontier, not size order; every n-bit code is visited once.
Python skeleton
def all_subsets(items):
n = len(items)
for mask in range(1 << n):
yield [items[i] for i in range(n) if mask >> i & 1]
def nonempty_submasks(mask):
sub = mask
while sub:
yield sub
sub = (sub - 1) & mask
def is_subset(a, b):
return a & b == a
Correctness sketch
n-bit strings and subsets of n positions are in bijection.
range(2^n) visits every encoding once.
sub-1 changes the lowest present bit and lower positions; AND with mask removes all outside bits.
The recurrence strictly decreases sub until zero.
Complexity
Time
Space
Parameters
O(2^n n) if every subset is materialized; O(3^n) over all masks and their submasks
O(n) for one generated subset
n selectable items
Edge cases
The empty set mask=0 often matters
1<<n grows rapidly
Decide whether a submask loop includes zero
Duplicate item values still occupy distinct positions
Parentheses make bit precedence explicit
Error patterns
Pattern
Why it fails / fix
Dropping the empty set
Starting masks at one loses a common base case.
Continuing after sub reaches zero
The recurrence wraps to mask and loops forever.
Assuming numeric order means size order
Adjacent masks need not have monotone popcount.
Selection and exclusion rules
Around twenty choices and all subsets matter: bitmask enumeration.
Need pruning or explicit solution paths: backtracking may read better.
Each set stores an optimum: bitmask DP.
For submasks of one mask, use the recurrence instead of rescanning all 2^n masks.