Medium · bitmask

Generate Subsets

Take the set {1, 2, 3} and ask of every element: in or out? That is a yes/no question, and a row of yes/no answers is a binary number. n elements give 2^n subsets — all of them reachable by counting from 1 to 2^n − 1.

At a glanceFor each mask from 1 to 2^n − 1, print every i whose bit is set (test with <code>mask % 2</code>, then <code>mask /= 2</code>) — no recursion needed.

Problem

Input: One integer n (1 ≤ n ≤ 8).

Output: Every non-empty subset of {1, …, n}, one per line, values in increasing order, subsets ordered by their binary mask (for n = 3: 1, 2, 1 2, 3, 1 3, 2 3, 1 2 3).

Samples:

Input	Output
`2`	`1 2 1 2`
`3`	`1 2 1 2 3 1 3 2 3 1 2 3`

The empty subset is mask 0, and the judge does not want a blank first line — start counting at 1. Values inside a subset come out in increasing order for free when you test bits from i = 1 upward.

Your solution

main.cpp — your solution

Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — Bit i means “i is in”

Agree that bit number i−1 of the mask (counting from 0) decides whether value i is printed. Mask 0b101 for n = 3 is the subset {1, 3}. Once the convention is fixed, printing a subset is just walking its bits.

Hint 2 — Decode bits with % and /

You do not need bit-shift operators: copy the mask into a temporary and peel it — if (m % 2 == 1) print i; then m /= 2; as i walks from 1 to n. This is exactly the digit-chopping loop from Binary Representation, pointed at bits instead of decimal digits.

Hint 3 — Build 2^n by multiplying

Start limit at 1 and double it n times (limit *= 2 in a loop). Then masks are 1 … limit - 1. For n = 8 that is 255 subsets — 2^n grows fast, and this problem only stays printable because the judge keeps n small.

Solution (try it first!)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int limit = 1;
    for (int i = 0; i < n; i++) limit *= 2;

    for (int mask = 1; mask < limit; mask++) {
        int m = mask;
        bool first = true;
        for (int i = 1; i <= n; i++) {
            if (m % 2 == 1) {
                if (!first) cout << " ";
                cout << i;
                first = false;
            }
            m /= 2;
        }
        cout << endl;
    }
    return 0;
}

The subset-as-bitmask trick is the backbone of brute force: when n ≤ 20, trying all 2^n subsets is a legitimate plan, and later it powers bitmask DP. Notice what you did not need: recursion. The counting loop in Binary Representation and this loop are the same machine pointed at different scales.

Deep dive

Why this works

A subset of {1..n} is one yes/no decision per element, and a fixed row of yes/no answers is a binary number. Counting masks 1..2^n−1 therefore enumerates every non-empty subset exactly once, and testing bit i−1 (m % 2, then m /= 2) tells you whether value i is in.

The cost

O(2^n × n) time — every mask decoded in O(n) — and O(1) extra space beyond the loop counters. n = 10 is 10,240 lines; n = 20 is already 20 million: brute force by bitmask has a hard ceiling.

Where it goes wrong

Starting the mask loop at 0 prints the empty subset as a blank first line the judge rejects — start at 1.
Forgetting the temporary: m /= 2 in the same expression that tests m % 2 eats the bit before you read it. Copy the mask, then peel.
Printing spaces after the last value instead of between values — the judge trims line ends, but a leading space before the first number is a wrong answer, not a style issue.

Next step

The same % / peel loop pointed at decimal numbers is Binary Representation; pointed at a number's 1-bits it is Bit Count. One loop, three problems.

Two things to remember

A subset of {1..n} is an n-bit number; bit i = 'i is in'.
2^n is the brute-force budget: n = 10 fine, n = 20 a million, n = 40 impossible.

🐞 This version fails — open it and try

Tests the bit before dividing — m /= 2 in the same line eats the bit it just read

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int limit = 1;
    for (int i = 0; i < n; i++) limit *= 2;
    for (int mask = 1; mask < limit; mask++) {
        int m = mask;
        for (int i = 1; i <= n; i++) {
            m /= 2;                  // bug: eats bit 0 before testing
            if (m % 2 == 1) cout << i << " ";
        }
        cout << endl;
        // also: trailing space instead of separators
    }
    return 0;
}