Combinations

A combination is a selection of elements where order does not matter. Unlike permutations, [1, 2] and [2, 1] represent the same combination.

Backtracking works naturally for combinations by progressively choosing elements and ensuring we never revisit earlier choices.

What Is a Combination?

Given:

[1, 2, 3]

All combinations of size 2 are:

[1, 2]
[1, 3]
[2, 3]

Notice that order is ignored.

The number of combinations is:

C(n, k) = n! / (k! · (n − k)!)

Why Backtracking Works Here

At each step:

• You choose the next element
• You move forward in the list
• You never go backward

This guarantees:

• No duplicates
• No reordered duplicates

Backtracking Strategy

State

• current → current combination being built
• start → index to begin choosing from

Base Case

• When current.len() == k, record the combination

Backtracking Template (Combinations)

backtrack(start):
    if current size == k:
        record result
        return

    for i from start to n:
        choose nums[i]
        backtrack(i + 1)
        undo choice

Rust Implementation

This example generates all combinations of size k.

pub fn combinations(nums: &[i32], k: usize) -> Vec<Vec<i32>> {
    let mut result = Vec::new();
    let mut current = Vec::new();

    backtrack(0, nums, k, &mut current, &mut result);
    result
}

fn backtrack(
    start: usize,
    nums: &[i32],
    k: usize,
    current: &mut Vec<i32>,
    result: &mut Vec<Vec<i32>>,
) {
    if current.len() == k {
        result.push(current.clone());
        return;
    }

    for i in start..nums.len() {
        current.push(nums[i]);
        backtrack(i + 1, nums, k, current, result);
        current.pop(); // undo
    }
}

Example Usage

fn main() {
    let nums = vec![1, 2, 3, 4];
    let result = combinations(&nums, 2);

    for combo in result {
        println!("{:?}", combo);
    }
}

Output:

[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]

Recursion Tree Intuition

For [1, 2, 3], k = 2:

[]
 ├─ [1]
 │   ├─ [1, 2]
 │   └─ [1, 3]
 └─ [2]
     └─ [2, 3]

Paths never revisit earlier elements.

Time and Space Complexity

Time Complexity

Space Complexity

Permutations vs Combinations

Common Mistakes

• Forgetting to advance start
• Generating duplicates
• Confusing combinations with subsets
• Incorrect base case

Variations

• Combinations with repetition
• Combination sum problems
• Subset generation (k varies)

These build directly on this pattern.

Summary

• Combinations ignore order
• Backtracking uses a start index
• Efficient pruning prevents duplicates
• Widely used in counting and selection problems

Playground Links

Rust - Combinations