Chapter 41

Home

Permutations and Combinations

Subsets don't care about order. Permutations do. For N elements, there are N! permutations — every possible ordering. Combinations are subsets of size K (order doesn't matter). Both are bread-and-butter backtracking patterns.

Subsets vs Permutations vs Combinations

Subsets (2ᴺ) { } {a} {b} {c} {a,b} {a,c} {b,c} {a,b,c} Permutations (N!) {abc} {acb} {bac} {bca} {cab} {cba} Combinations (C(N,K)) K=2: {a,b} {a,c} {b,c}

Subset — any collection, any size, order irrelevant

Permutation — all elements, every possible order

Combination — exactly K elements, order irrelevant

Generating Permutations (Backtracking)

Instead of include/exclude, at each position you choose which unused element goes there. Track used elements with a boolean array or set.

C++ — recursive permutations

void permute(vector<int>& nums, vector<bool>& used,
             vector<int>& current, vector<vector<int>>& result) {
    if (current.size() == nums.size()) {
        result.push_back(current);
        return;
    }
    for (int i = 0; i < nums.size(); i++) {
        if (used[i]) continue;
        used[i] = true;
        current.push_back(nums[i]);
        permute(nums, used, current, result);
        current.pop_back();
        used[i] = false;     // backtrack
    }
}

Rust — recursive permutations

fn permute(nums: &[i32]) -> Vec<Vec<i32>> {
    let mut result = Vec::new();
    let mut current = Vec::new();
    let mut used = vec![false; nums.len()];
    backtrack(nums, &mut used, &mut current, &mut result);
    result
}

fn backtrack(nums: &[i32], used: &mut Vec<bool>,
             current: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
    if current.len() == nums.len() {
        result.push(current.clone());
        return;
    }
    for i in 0..nums.len() {
        if used[i] { continue; }
        used[i] = true;
        current.push(nums[i]);
        backtrack(nums, used, current, result);
        current.pop();
        used[i] = false;
    }
}

💡 Used-array backtracking

The used[] array is swapped in and out of scope by the backtrack. Before recursing, mark the element as used. After returning, unmark it. This is the permutation-specific version of the push/pop pattern from subset generation.

C++ Shortcut: next_permutation

C++ provides std::next_permutation — it generates the next permutation in lexicographic order. Start with a sorted array and call it in a loop.

C++ — next_permutation

vector<int> nums = {1, 2, 3};
do {
    for (int x : nums) cout << x << " ";
    cout << "\n";
} while (next_permutation(nums.begin(), nums.end()));

// Output: 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1

📐 Rust doesn't have next_permutation built-in

In Rust, implement the backtracking pattern above, or use a crate like permutations. For contests, many Rust programmers keep a next_permutation port in their template — it's ~15 lines.

Combinations of Size K

Combinations are subsets with exactly K elements. The recursive pattern is subset generation with an early stop: when current.size() == K, record it and return.

C++ — combinations (C(N,K))

void combine(int n, int k, int start, vector<int>& cur,
             vector<vector<int>>& res) {
    if (cur.size() == k) {
        res.push_back(cur);
        return;
    }
    for (int i = start; i <= n; i++) {
        cur.push_back(i);
        combine(n, k, i + 1, cur, res);  // next start = i+1
        cur.pop_back();
    }
}

Rust — combinations

fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
    let mut result = Vec::new();
    let mut current = Vec::new();
    backtrack(n, k, 1, &mut current, &mut result);
    result
}

fn backtrack(n: i32, k: i32, start: i32,
             current: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
    if current.len() == k as usize {
        result.push(current.clone());
        return;
    }
    for i in start..=n {
        current.push(i);
        backtrack(n, k, i + 1, current, result);
        current.pop();
    }
}

💡 The start parameter prevents repeats

In permutations, any unused element can go next. In combinations, elements must be chosen in increasing order (by index). The start parameter enforces this — once you pick element 3, only elements > 3 are considered. This prevents both duplicates and the permutation explosion.

Key Takeaways

Practice