Skip to content

Generating Subsets

Generating subsets means enumerating all ways to choose a subcollection of elements from a finite set (including the empty set and the full set). For \(n\) distinct items there are \(2^n\) subsets. This page ties together patterns used in complete search: bitmask loops, recursion, and fixed-size combinations.

All subsets with a bitmask

For \(n\) small enough that \(2^n\) is feasible (often \(n \le 20\)–\(22\)), iterate mask from 0 to (1 << n) - 1. Bit j of mask is 1 if the \(j\)-th element is included.

#include <vector>
using namespace std;

// indices 0..n-1; build one subset per mask
vector<int> subsetFromMask(const vector<int>& a, int mask) {
    vector<int> s;
    for (int j = 0; j < (int)a.size(); ++j)
        if (mask & (1 << j)) s.push_back(a[j]);
    return s;
}

void enumerateAllSubsets(const vector<int>& a) {
    int n = (int)a.size();
    for (int mask = 0; mask < (1 << n); ++mask) {
        vector<int> s = subsetFromMask(a, mask);
        // use s: check property, update answer, etc.
    }
}

See Boolean Counter Enumeration for the same idea framed as binary counting and a subset-sum style example.

Recursive generation

Equivalent to the bitmask: at each index, either skip or take the element. Useful when you want to stream subsets without building all masks, or when combining with pruning early.

void genSubsets(int i, const vector<int>& a, vector<int>& cur,
                vector<vector<int>>& out) {
    if (i == (int)a.size()) {
        out.push_back(cur);
        return;
    }
    genSubsets(i + 1, a, cur, out);      // don't take a[i]
    cur.push_back(a[i]);
    genSubsets(i + 1, a, cur, out);      // take a[i]
    cur.pop_back();
}

Combinations (fixed-size subsets)

Often you need only subsets of exactly \(k\) elements (\(\binom{n}{k}\) choices), not all \(2^n\). Build by picking positions in increasing order.

void combinations(int start, int k, const vector<int>& a, vector<int>& cur,
                  vector<vector<int>>& out) {
    if ((int)cur.size() == k) {
        out.push_back(cur);
        return;
    }
    for (int i = start; i < (int)a.size(); ++i) {
        cur.push_back(a[i]);
        combinations(i + 1, k, a, cur, out);
        cur.pop_back();
    }
}

Duplicates in the input

If values can repeat, sort first and skip equal neighbors in the same recursion level when generating combinations, or use frequency maps for multiset subsets (similar to distinct permutations on the permutation page).

Complexity

Task Count Typical time
All subsets \(2^n\) \(O(2^n \cdot n)\) if you materialize each subset
All \(k\)-subsets \(\binom{n}{k}\) \(O(\binom{n}{k} \cdot k)\)
Single subset from mask — \(O(n)\)

When to use which

  • Bitmask: \(n\) small, need all subsets or DP over subsets.
  • Recursion: easy to add Search Pruning or build only valid subsets.
  • Combinations: “choose \(k\)” problems without scanning \(2^n\).