Refactoring: Bitmask Subsets

Every subset can be represented as a binary number — bit i = 1 means "include element i." Instead of recursive backtracking, iterate from 0 to 2ᴺ−1 and read the bits. No stack, no backtracking, just a loop.

The Bitmask Idea

For N = 3, the numbers 0–7 in binary represent every subset:

Before: Recursive Backtracking

C++ — recursive (from ch.39)

void subsets(vector<int>& nums, int i, vector<int>& cur, vector<vector<int>>& res) {
    if (i == nums.size()) { res.push_back(cur); return; }
    subsets(nums, i + 1, cur, res);           // exclude
    cur.push_back(nums[i]);
    subsets(nums, i + 1, cur, res);           // include
    cur.pop_back();
}

🚨 Recursion overhead

For N = 20, this makes 2ᴺ⁺¹ − 1 ≈ 2 million function calls. Each call has overhead (stack frame, parameter passing). The bitmask approach replaces all calls with one loop — no function call overhead, no stack depth.

After: Iterative Bitmask Enumeration

C++ — O(N × 2ᴺ) iterative bitmask

vector<vector<int>> subsets(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> result;

    for (int mask = 0; mask < (1 << n); mask++) {
        vector<int> current;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i))   // bit i is set?
                current.push_back(nums[i]);
        }
        result.push_back(current);
    }
    return result;
}

Rust — iterative bitmask

fn subsets(nums: &[i32]) -> Vec<Vec<i32>> {
    let n = nums.len();
    let mut result = Vec::new();

    for mask in 0..(1 << n) {
        let mut current = Vec::new();
        for i in 0..n {
            if mask & (1 << i) != 0 {
                current.push(nums[i]);
            }
        }
        result.push(current);
    }
    result
}

💡 Reading bits with mask & (1 << i)

1 << i creates a number with only bit i set (1, 2, 4, 8, …). mask & (1 << i) checks if that bit is on in the mask. Non-zero = include element i. Zero = skip it.

📐 When to use which

Bitmask is faster and simpler for generating all subsets. Use it when N ≤ 25 and you need every subset. Recursive backtracking is more flexible — it lets you prune branches early (skip bad subsets without iterating all 2ᴺ). Use it when you have constraints that can cut off large parts of the search space.

Key Takeaways

→ Bitmask = each bit represents "include element at this index."
→ Iterate mask = 0 .. (1<<N), check each bit with mask & (1<<i).
→ No recursion, no stack frames, no backtracking — just loops.
→ Use recursive when you need pruning. Use bitmask when you need all subsets.