cf.completefrontend
BIT MANIPULATION · CORE

Enumerating subsets with bitmasks

Go through every subset of n items by counting from 0 to 2^n - 1 and reading each number's bits as "in" or "out".

Time O(2^n × n)Space O(2^n)5 practice problemsStep-through picture

The idea

A subset of n items can be written as n bits: bit i is 1 if item i is in the subset. For 3 items, 101 means items 0 and 2 are in. Such a number is called a bitmask, or just a mask.

Every whole number from 0 to 2^n - 1 is a different mask, and together they cover every subset exactly once. So a simple for loop over mask visits all subsets, with no recursion. Inside, mask & (1 << i) tells you whether item i is in.

Masks are also handy to store: a subset of up to 31 items fits in one number, and two subsets can be combined with | (union), & (intersection), or compared with ===. A related trick, sub = (sub - 1) & mask, walks through just the subsets of a given mask.

An everyday example

Counting with fingers raised

Hold up your fingers to count in binary: each finger is up (1) or down (0). Counting from 0 to 7 with three fingers raises every possible combination of those fingers, each exactly once. If each finger stands for an item, counting up visits every group of items.

How the example maps to the code
In the exampleIn the code
Your fingersthe n items
A combination of raised fingersmask
Counting up onemask++
Is finger i raised?mask & (1 << i)
All fingers raised(1 << n) - 1

From the slow way to enumerating subsets with bitmasks

  1. Start with the usual way to visit every subset: a recursive function that, for each item, first skips it and then takes it. It works, but it needs a helper with extra parameters, a call stack, and some way to name the current subset, often an array that gets copied.
  2. Look at what a subset really is: for each of the n items, a yes or a no. That's n yes/no answers in a row, which is exactly what n bits are. Write bit i as 1 when item i is in. For [4, 10, 3], the subset with items 0 and 2 is 101.
  3. Every pattern of n bits is a whole number from 0 to 2^n - 1, and every such number is a different pattern. So counting from 0 to 2^n - 1 walks through every subset exactly once, with no recursion and no copies. The subset is just the number mask.
  4. Inside the loop, mask & (1 << i) is non-zero exactly when item i is in, so an inner loop over i can add up the subset or build it. A last trick, sub = (sub - 1) & mask, jumps straight to the next smaller subset of a given mask. The counting loop is subset enumeration with bitmasks.

How it works

  1. Let n be the number of items. The masks go from 0 to (1 << n) - 1.
  2. Loop mask from 0 while mask < 1 << n.
  3. For each mask, loop i from 0 to n - 1. If mask & (1 << i) is non-zero, item i is in this subset.
  4. Do the work for this subset, such as adding up items[i] into sum.
  5. To list only the subsets of a given mask, start with sub = mask and step with sub = (sub - 1) & mask until it reaches 0, then add 0 itself.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function subsetSums(items) {
  2. const n = items.length;
  3. const sums = [];
  4. for (let mask = 0; mask < 1 << n; mask++) {
  5. let sum = 0;
  6. for (let i = 0; i < n; i++) {
  7. if (mask & (1 << i)) sum += items[i];
  8. }
  9. sums.push(sum);
  10. }
  11. return sums;
  12. }
  14. function submasks(mask) {
  15. const result = [];
  16. for (let sub = mask; sub > 0; sub = (sub - 1) & mask) {
  17. result.push(sub);
  18. }
  19. result.push(0);
  20. return result;
  21. }

How fast it is

TimeO(2^n × n)
Extra memoryO(2^n)

There are 2^n masks and each one checks n bits. The sums array has one entry per mask.

  • Best caseO(2^n × n)

    Every list of n items does the same work: 2^n masks, each checking n bits. Only n matters, not the values.

  • Average caseO(2^n × n)

    For 20 items: 1,048,576 masks times 20 checks, about 21 million steps, fine in a browser.

  • Worst caseO(2^n × n)

    Larger n. Each extra item doubles the work, so 30 items is about 1,500 times slower than 20: 2^10 times more masks, each with more bits to check. submasks(mask) alone is cheaper: O(2^k) for a mask with k bits set.

Common mistakes

  • Writing mask & 1 << i === 0. Comparison runs before &, so add brackets: (mask & (1 << i)) === 0.
  • Using it for n above about 25. 2^25 is over 33 million subsets, which is slow, and 1 << 31 turns negative.
  • Treating bit 0 as the leftmost item. Bit 0 is the rightmost bit; just be consistent between building and reading masks.
  • Forgetting the empty subset when walking submasks: the loop stops at 0 without visiting it.

When to use it

Look for these clues in a problem:

  • The input has at most about 20 items and you need to check every subset.
  • Each item is either chosen or not, and you need the best, a count, or all valid choices.
  • Sets of up to 31 small things (skills, permissions, features) need to be compared or combined quickly.
  • A dynamic programming state is "which items are used so far" (that's bitmask DP).

Check yourself

Answer each one in your head first, then open it.

Which mask stands for items 0 and 2 of [4, 10, 3], and what is its sum?

5, which is 101 in binary. Its sum is 4 + 3 = 7, stored at sums[5].

How many masks does a list of 20 items have?

2^20 = 1,048,576, one for each subset, including the empty one.

Why does subsetSums with 31 items return an empty array?

1 << 31 is negative in JavaScript, so mask < 1 << n is false at once and the loop never runs.

Why does submasks push 0 after the loop?

The loop condition is sub > 0, so it stops as soon as sub becomes 0, before pushing it. The empty subset is added separately.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 5 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Subsets and masks match one to one. Each subset gives exactly one pattern of n bits, and each pattern is exactly one number from 0 to 2^n - 1. The loop mask = 0, 1, 2, ... visits each of those numbers once, so it visits each subset once, with none missed and none repeated.

Inside, 1 << i has only bit i set, so mask & (1 << i) is non-zero exactly when bit i of mask is 1, which means item i is in the subset. So sum adds exactly the subset's items. Because subsets are visited in mask order, sums[mask] is that subset's sum, and any subset's answer can be looked up later by its mask.

For submasks, subtracting 1 from sub turns its lowest 1 into 0 and every 0 below it into 1. That's the next smaller number, but it may have bits outside mask; & mask removes them. The result is the largest subset of mask below sub, so the walk visits every subset of mask in decreasing order, each once. The loop stops at 0, so 0 is pushed after it.

Going deeper

3 more ideas

Why every subset appears once

Each subset gives exactly one pattern of n bits, and each pattern is exactly one number from 0 to 2^n - 1. So counting through those numbers visits each subset once, with no repeats and no gaps.

Walking through the subsets of a mask

Subtracting 1 from sub turns its lowest 1 into 0 and the 0s below into 1s; & mask then drops any bit that isn't in mask. The result is the next smaller subset of mask. For mask = 101: 101, then 100, then 001, then 000. Summed over all masks of n bits, this visits 3^n pairs, which is the basis of many bitmask DP solutions.

The cost and the limit

There are 2^n masks and each one checks n bits, so the time is O(2^n × n). That is about 20 million steps for n = 20, fine in a browser. For n = 30 it's 30 billion, far too slow. Also, 1 << 31 is negative in JavaScript, so this loop only works for n up to 30.

Work it by hand

Every step in a table, with why

List the sum of every subset of [4, 10, 3], then walk the subsets of the mask 110.

subsetSums([4, 10, 3]), then submasks(6)

StepmaskBitsItems insumWhat happensWhy
10000none0the empty subsetNo bit is set, so the inner loop adds nothing.
2100104only item 0Bit 0 is the rightmost bit. items[0] is 4.
32010110only item 12 & (1 << 1) is non-zero, so items[1] is added.
430110, 114items 0 and 14 + 10. Counting up to 3 added item 0 back in.
5410023only item 2Each time the count reaches a power of two, a new item appears on its own.
651010, 27items 0 and 24 + 3.
761101, 213items 1 and 210 + 3.
871110, 1, 217every itemmask + 1 is 8, which equals 1 << 3, so the loop ends after this.
9sub = 61101, 2-push 6submasks(6) starts with the mask itself.
10sub = 41002-(6 - 1) & 66 - 1 is 101; ANDing with 110 drops bit 0, which isn't in the mask, giving 100.
11sub = 20101-(4 - 1) & 64 - 1 is 011; ANDing with 110 gives 010.
12sub = 0000none-loop ends, push 0(2 - 1) & 6 is 0, so the loop stops. The empty subset is pushed after the loop.

subsetSums returns [0, 4, 10, 14, 3, 7, 13, 17], where sums[mask] is the sum of subset mask. submasks(6) returns [6, 4, 2, 0]: the 4 subsets of {1, 2}, from largest to smallest.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Enumerating subsets with bitmasksO(2^n × n)O(2^n)Up to about 20-25 items when you want every subset with a simple loop and a number to name each one.
Recursive include or skipO(2^n)O(n)You build each subset step by step, or want to cut off branches early (backtracking).
Reuse smaller subsetsO(2^n)O(2^n)You need a value for every subset and each one follows from a smaller subset.

Extra memory: O(2^n): the sums array has one entry per subset. Just visiting subsets without storing them needs only O(1).

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Enumerating subsets with bitmasks and the other approaches, on a scale where each line up is 10 times more steps.
  • Enumerating subsets with bitmasks O(2^n × n)
  • Recursive include or skip, Reuse smaller subsets O(2^n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Enumerating subsets with bitmasks10,240more than a quadrillionmore than a quadrillion
Recursive include or skip1,024more than a quadrillionmore than a quadrillion
Reuse smaller subsets1,024more than a quadrillionmore than a quadrillion

Inputs that need care

5 tricky inputs
No items: subsetSums([])
1 << 0 is 1, so the loop runs once for mask = 0 and returns [0]: the empty subset, whose sum is 0.
31 items
1 << 31 is -2147483648, so mask < 1 << n is false at once and it returns [] without warning. It would be far too slow anyway; keep n to about 25.
32 items
1 << 32 wraps to 1, so only mask = 0 runs and it returns [0]. Again silent; check n before looping.
Equal items: [5, 5]
Returns [0, 5, 5, 10]. Masks 01 and 10 are different subsets (by position) with the same sum. Put the sums in a Set if only distinct sums matter.
submasks(0)
The loop doesn't run, since sub > 0 is false, and it returns [0]: the empty set is the only subset of the empty set.

Variations and follow-ups

Twists interviewers add

Reuse smaller subsets

sums[mask] equals sums[mask ^ low] plus the item at bit low, where low = mask & -mask is the lowest set bit. The item index is 31 - Math.clz32(low). Each mask then costs one step, so the whole table takes O(2^n) instead of O(2^n × n).

Bitmask dynamic programming

Use the mask as part of a DP state: "the best cost having visited exactly these cities", stored as dp[mask][last]. Problems with up to about 20 items, like assigning tasks to people or visiting every stop once, become O(2^n × n²) instead of O(n!).

Meet in the middle

For about 40 items, split them into two halves of 20, list each half's 2^20 subset sums, and combine the two lists with sorting and two pointers. That's two million subsets instead of a trillion.

Gray code order

Visiting masks in the order mask ^ (mask >> 1) changes exactly one item between neighbors: 000 001 011 010 110 111 101 100. When adding or removing one item is cheap, each step costs O(1).

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from a small n ("n <= 20"), "try every combination", "every subset", "choose any group of items", or a state that is "which items are used so far".
  • Explain it as: "Each of the 2^n numbers below 1 << n is one subset, where bit i says whether item i is in. I loop over them and read the bits." Then state the cost, O(2^n × n).
  • Test n = 0 and a small case of 2 or 3 items by writing out the masks in binary. Mention the limit: past 30 items, 1 << n breaks in JavaScript.
  • A common follow-up is "list the subsets of a given mask". Show sub = (sub - 1) & mask, and remember to add 0 at the end.

Where frontend code uses it

The same idea in real UI code
  • Testing every on/off combination of a few feature flags or component props is a loop over masks.
  • A form with up to ~16 optional checkboxes can store its state as one mask number, which is easy to put in a URL and compare.
  • Node.compareDocumentPosition returns a bitmask such as DOCUMENT_POSITION_CONTAINS | DOCUMENT_POSITION_PRECEDING, read with & checks like these.

Related algorithms