Backtracking

Permutations

For each position, try placing every unused element there, then recurse for the remaining positions. This generates all n! orderings. Use a 'used' set or swap elements to track what's available.

O(n!)

O(n)

How It Works

Permutations fill positions one at a time: for the current position, try every element not yet used, place it, recurse to fill the next position, then remove it and try the next candidate. A boolean used array (or membership check against the current path) tracks availability; alternatively, swapping the chosen element into the current index and swapping back afterward avoids the extra array. The recursion tree has n choices at the first level, n-1 at the next, bottoming out in n! complete orderings.

Output size dictates cost: n! permutations of length n mean O(n * n!) total work, so the algorithm is output-optimal. Auxiliary space is O(n) for the path and used markers. For inputs with duplicates, sort first and skip a value when it equals its predecessor and that predecessor is still unused at this level — this collapses interchangeable branches before they spawn.

Step-by-Step Visualization

Generate all permutations of [1,2,3]

Total3! = 6

1/3

Code

Java

static List<List<Integer>> permute(int[] nums) {
  List<List<Integer>> result = new ArrayList<>();
  backtrack(nums, new ArrayList<>(), new boolean[nums.length], result);
  return result;
}

static void backtrack(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> result) {
  if (path.size() == nums.length) { result.add(new ArrayList<>(path)); return; }
  for (int i = 0; i < nums.length; i++) {
    if (used[i]) continue;
    used[i] = true;
    path.add(nums[i]);
    backtrack(nums, path, used, result);
    path.remove(path.size() - 1);
    used[i] = false;
  }
}

Tips & Gotchas

1For each position, try every unused element

2Use a visited set or swap elements in-place

3n! total permutations for n elements

Practice Problems

1Permutations
2Permutations II
3Letter Tile Possibilities
4Beautiful Arrangement
5Next Permutation

About the Backtracking Pattern

Systematically explore all possible solutions by making choices one at a time. If a choice leads to a dead end, undo it (backtrack) and try the next option. Think of it as exploring a decision tree — you go deep, and come back up when stuck.

Key insight

Every recursive solution has: base case, recursive case, and combining step. For backtracking, add: make choice → recurse → undo choice. Prune early to avoid TLE.

Common Recursion Interview Problems

Subsets
Permutations
Combination Sum
N-Queens
Word Search
Generate Parentheses
Letter Combinations of Phone Number

Frequently Asked Questions

Should I use a used array or the swap technique?

Both are correct and O(n * n!). The used-array version keeps the input intact and produces permutations in lexicographic order when the input is sorted, which some problems require. Swapping saves the extra array but scrambles ordering and makes duplicate handling harder, so prefer used-array when duplicates exist.

How do permutations differ structurally from subsets in backtracking?

Subsets decide include-or-skip per element, so order does not matter and a start index prevents revisiting; the tree has 2^n leaves. Permutations decide which element goes in each position, so every unused element is a candidate at every level, giving n! leaves. Confusing the two loop structures is a classic interview slip.