Permutations

Backtracking with a used-mask

Backtracking with a ‘used’ set. Draw the decision tree.

Published Apr 16, 2026

Problem

Given an array of distinct integers, return all possible permutations.

Input

nums = [1, 2, 3]

Output

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

Input

nums = [0, 1]

Output

[[0,1],[1,0]]

Input

nums = [1]

Output

[[1]]

Intuition

A permutation picks an element for position 0, then position 1, then position 2, and so on — each pick must be from the elements not yet used. That's the backtracking template with one twist: you need a way to ask "have I used this element already?".

Two answers: a boolean used[] array, or swap the picked element into the current prefix in place. Both give you n! leaves. The swap trick is elegant — no extra bookkeeping — but mutates the input and produces permutations in a different order than the used[] version.

There are n! permutations and each one costs O(n) to copy into the result — hence O(n · n!).

Approach

Backtracking with used[]

TimeO(n · n!)

SpaceO(n)

Recommended

For each recursive call, try every index that's not yet marked used. Mark, recurse, unmark.

impl Solution {
    pub fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut out = Vec::new();
        let mut path = Vec::with_capacity(nums.len());
        let mut used = vec![false; nums.len()];
        fn dfs(
            nums: &[i32],
            used: &mut [bool],
            path: &mut Vec<i32>,
            out: &mut Vec<Vec<i32>>,
        ) {
            if path.len() == nums.len() {
                out.push(path.clone());
                return;
            }
            for i in 0..nums.len() {
                if used[i] {
                    continue;
                }
                used[i] = true;
                path.push(nums[i]);
                dfs(nums, used, path, out);
                path.pop();
                used[i] = false;
            }
        }
        dfs(&nums, &mut used, &mut path, &mut out);
        out
    }
}

Rust · runnable

function permute(nums: number[]): number[][] {
  const out: number[][] = [];
  const path: number[] = [];
  const used = new Array(nums.length).fill(false);
  const dfs = (): void => {
    if (path.length === nums.length) {
      out.push(path.slice());
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      path.push(nums[i]);
      dfs();
      path.pop();
      used[i] = false;
    }
  };
  dfs();
  return out;
}

TypeScript · runnable

Swap in place

TimeO(n · n!)

SpaceO(n)

Maintain a start index — the length of the prefix we've committed. Swap any element from positions start..n into position start, recurse with start + 1, swap back.

The input is mutated during the walk, but restored before each return. No used array, no path array — just the nums itself.

impl Solution {
    pub fn permute(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut out = Vec::new();
        fn dfs(start: usize, nums: &mut Vec<i32>, out: &mut Vec<Vec<i32>>) {
            if start == nums.len() {
                out.push(nums.clone());
                return;
            }
            for i in start..nums.len() {
                nums.swap(start, i);
                dfs(start + 1, nums, out);
                nums.swap(start, i);
            }
        }
        dfs(0, &mut nums, &mut out);
        out
    }
}

Rust · runnable

function permute(nums: number[]): number[][] {
  const out: number[][] = [];
  const dfs = (start: number): void => {
    if (start === nums.length) {
      out.push(nums.slice());
      return;
    }
    for (let i = start; i < nums.length; i++) {
      [nums[start], nums[i]] = [nums[i], nums[start]];
      dfs(start + 1);
      [nums[start], nums[i]] = [nums[i], nums[start]];
    }
  };
  dfs(0);
  return out;
}

TypeScript · runnable

Trace

Backtracking with used[] on nums = [1, 2, 3] — first branch only:

step	path	used	action
1	[]	[F,F,F]	try 1
2	[1]	[T,F,F]	try 2
3	[1,2]	[T,T,F]	try 3
4	[1,2,3]	[T,T,T]	emit
5	[1,2]	[T,T,F]	pop
6	[1]	[T,F,F]	try 3
7	[1,3]	[T,F,T]	try 2
8	[1,3,2]	[T,T,T]	emit

The tree has 3! = 6 leaves. Each complete path is copied into the output.

Edge cases

Empty input — return [[]] (one empty permutation).
Single element — return [[x]].
Duplicates in input — this problem says distinct. If duplicates were allowed (#47), you'd sort first and skip duplicate siblings with i > start && nums[i] == nums[i-1] && !used[i-1].

Takeaway

Permutations vs. subsets is the right mental split. Subsets choose whether each element appears; permutations choose the order. Both use the backtracking template — the choices and emission rule change. Once you can write both cleanly, combinations (#39) and partitions (#131) are straightforward variations on "choose with a start pointer" vs. "choose by length".

Medium#78

Subsets

The canonical backtracking template. Include or exclude each element.

Medium#39

Combination Sum

Unbounded choices. How do you avoid duplicates?

Medium#131

Palindrome Partitioning

Backtrack on where to cut. Precompute palindrome checks with DP.