Permutations

A permutation is an arrangement of elements in a specific order. Unlike combinations or subsets, order matters in permutations.

Backtracking is the natural technique for generating permutations because it explores all possible orderings by making choices step by step and undoing them afterward.

What Is a Permutation?

Given a list:

[1, 2, 3]

Some permutations are:

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

For n elements, there are:

n! (factorial) permutations

Why Backtracking Works Here

At each position, you can choose any unused element.

The algorithm:

1. Pick an unused element
2. Add it to the current path
3. Recurse
4. Remove it (backtrack)

This explores all valid orderings.

Backtracking Strategy

State

• current → current permutation being built
• used → tracks which elements are already included

Base Case

• When current.len() == nums.len(), record a permutation

Backtracking Template (Permutations)

backtrack():
    if current is complete:
        record result
        return

    for each element:
        if not used:
            mark used
            add to current
            backtrack()
            undo choice

Rust Implementation

pub fn permutations(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();      // undo choice
        used[i] = false;    // mark unused
    }
}

Example Usage

fn main() {
    let nums = vec![1, 2, 3];
    let perms = permutations(&nums);

    for p in perms {
        println!("{:?}", p);
    }
}

Output:

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

How the Recursion Tree Looks

For [1, 2]:

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

Each level fixes one position in the permutation.

Time and Space Complexity

Time Complexity

Space Complexity

Common Mistakes

• Forgetting to undo (used[i] = false)
• Reusing elements unintentionally
• Modifying shared state incorrectly
• Expecting permutations to scale to large n

Variations

• Permutations with duplicate elements (needs pruning)
• In-place swapping approach
• Generating next permutation lexicographically

These build directly on this foundation.

Summary

• Permutations consider order
• Backtracking explores all arrangements
• Uses a used array to avoid repetition
• Time complexity grows factorially

Playground Links

Rust - Permutations