Chapter 39

Home

Generating All Subsets

For every element in a set, you have two choices: include it or exclude it. The set of all choices — all subsets — is the power set. For N elements, there are 2ᴺ subsets. Generating them recursively is the foundation of backtracking.

The Include/Exclude Decision Tree

Think of each element as a fork in the road. At element i, you branch: take it or skip it. By the time you've made N decisions, you have one subset. Branching at every step gives 2ᴺ leaves.

start include ① exclude ① include ② exclude ② ... and so on 2ᴺ leaves = every possible subset

C++ — recursive subset generation

void subsets(vector<int>& nums, int i, vector<int>& current, vector<vector<int>>& result) {
    if (i == nums.size()) {
        result.push_back(current);  // base: no more decisions
        return;
    }

    // Branch 1: exclude nums[i]
    subsets(nums, i + 1, current, result);

    // Branch 2: include nums[i]
    current.push_back(nums[i]);
    subsets(nums, i + 1, current, result);
    current.pop_back();  // backtrack
}

// Usage:
vector<vector<int>> result;
vector<int> current;
subsets(nums, 0, current, result);

Rust — recursive subset generation

fn subsets(nums: &[i32]) -> Vec<Vec<i32>> {
    let mut result = Vec::new();
    let mut current = Vec::new();
    backtrack(nums, 0, &mut current, &mut result);
    result
}

fn backtrack(nums: &[i32], i: usize,
             current: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
    if i == nums.len() {
        result.push(current.clone());
        return;
    }
    // Exclude
    backtrack(nums, i + 1, current, result);
    // Include
    current.push(nums[i]);
    backtrack(nums, i + 1, current, result);
    current.pop();  // backtrack
}

💡 The backtracking pattern

push() before recursing, pop() after — that's the backtrack. You're exploring a possibility, then undoing it so the next branch starts from a clean state. Without pop_back(), elements from one branch would leak into the next.

What 2ᴺ Means in Practice

// N=10:  1,024 subsets   — instant
// N=20:  1,048,576        — < 0.1s
// N=30:  1,073,741,824    — ~10 seconds
// N=40:  ~10¹²            — hours

Subset generation is O(2ᴺ) and that's unavoidable. The constraint matters: if a problem says N ≤ 20, subset enumeration is likely the intended solution. If N ≤ 30, you'll need pruning or bitmask tricks (next chapter).

Key Takeaways

Practice