Published by Dimitris Kougioumtzis · Updated
Enumerate each membership mask exactly once. Bit i indicates whether input position i belongs to the subset.
Count from zero through 2^n minus one. Interpret bit i of each mask as the membership flag for input position i, obtaining every subset exactly once.
When to use Subset enumeration by bit masks
Enumerating a small power set for exhaustive search and bit-mask dynamic programming.
Choosing an alternative
Combinations restrict cardinality to k. Subset enumeration visits every cardinality, including the empty and complete subsets; Gray code uses a different order with single-bit changes.
Worked example: input and state changes
Example input
2,4,6
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Input positions 2,4,6. Membership is not assigned yet.
State at this checkpoint
{ "values": [ -1, -1, -1 ], "active": [], "kind": "matrix", "columns": 3, "result": 0, "output": [] }Step 2: Mask 1: {2}.
State at this checkpoint
{ "values": [ 1, 0, 0 ], "active": [], "kind": "matrix", "columns": 3, "result": 2, "output": [ 0, 1 ] }Step 4: Mask 3: {2,4}.
State at this checkpoint
{ "values": [ 1, 1, 0 ], "active": [], "kind": "matrix", "columns": 3, "result": 4, "output": [ 0, 1, 2, 3 ] }Step 6: Mask 5: {2,6}.
State at this checkpoint
{ "values": [ 1, 0, 1 ], "active": [], "kind": "matrix", "columns": 3, "result": 6, "output": [ 0, 1, 2, 3, 4, 5 ] }Step 8: Mask 7: {2,4,6}.
State at this checkpoint
{ "values": [ 1, 1, 1 ], "active": [], "kind": "matrix", "columns": 3, "result": 8, "output": [ 0, 1, 2, 3, 4, 5, 6, 7 ] }
Expected final state
Mask 7: {2,4,6}.
Complexity and input bounds
Family: Combinatorics. Time complexity: O(n 2^n) displayed membership.
Implementation detail: The view accepts at most seven values and displays a zero/one membership row for each mask. Downloads take only the number of labeled positions, return 2^n and write the masks in ascending order. Callers map selected positions to their values. The empty universe has the one empty subset.
Space complexity: O(1) mask-generation scratch excluding output; expanding memberships takes O(n), and saved frames add space.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
1..7 values 0..99. Duplicate values retain distinct positions; downloads enumerate index masks.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Duplicate values still occupy distinct labeled positions. Include mask zero. Counts grow exponentially, so keep the input universe bounded.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 | // n 0..7 labeled input positions. Returns 2^n and writes every subset membership mask in ascending order; bit i selects position i. Output capacity at least 2^n, at most 128. Empty universe has one empty subset, mask 0. Values are supplied by callers when interpreting masks. O(2^n) time to emit masks and O(1) scratch; expanding all memberships costs O(n*2^n). Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(n, output) { let count = 1 << n; for (let mask = 0; mask < count; mask++) { output[mask] = mask; } return count; } |
Source
Author reference for combinatorial generation, not a claim to an original research paper. The playground specifies its own bounded enumeration order and duplicate/position semantics.
- The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1
Donald E. Knuth (2011). Author reference book.