LeetCode #46 — Medium

Permutations

A complete visual walkthrough of the backtracking approach — building a decision tree to generate every arrangement.

Patterns Used
🔀Backtracking→

Roadmap

  1. The Brute Force Idea
  2. The Core Insight — Backtracking with Used Array
  3. Walkthrough — Decision Tree for [1,2,3]
  4. Edge Cases
  5. Full Annotated Code
  6. Interactive Demo
  7. Complexity Analysis
Step 01

The Brute Force Idea

To generate all permutations, we need to place each element in each possible position. For n elements, the first position has n choices, the second has n-1, and so on.

Counting Permutations

n = 1
1 permutation
n = 3
3! = 6 permutations
n = 6
6! = 720 permutations

We can't avoid generating all n! permutations — that's the output size. But we can generate them efficiently using a systematic exploration strategy.

💡

Backtracking is the standard template for exhaustive enumeration problems. Build a candidate solution incrementally, and "undo" (backtrack) each choice before trying the next one. This avoids creating n! separate arrays upfront.

Step 02

The Core Insight — Backtracking with Used Array

We maintain a path (current partial permutation) and a used boolean array to track which elements are already placed.

The Backtracking Template

1. Base case: path.size() == n
All positions filled — add a copy of path to the result.
2. Choose: try each unused element
For each nums[i] where used[i] == false: mark it used, add to path.
3. Explore: recurse to fill next position
Call backtrack() recursively to continue building the permutation.
4. Unchoose: backtrack
Remove from path, mark used[i] = false. Now try the next element.
⚡

Why copy the path? We add new ArrayList<>(path) because path is mutated during backtracking. Without the copy, all entries in the result would reference the same (eventually empty) list.

Step 03

Walkthrough — Decision Tree for [1,2,3]

Each level of the tree represents choosing which element to place at that position. Leaves are complete permutations.

The Decision Tree

[ ]
choose 1st element
/    |    \
[1]
[2]
[3]
choose 2nd element
/   \        /   \        /   \
[1,2]
[1,3]
[2,1]
[2,3]
[3,1]
[3,2]
choose 3rd (last) element
|     |       |     |       |     |
[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]
6 complete permutations (3! = 6)

Backtracking Trace for the [1,2,3] Branch

choose 1 path=[1] used=[T,F,F]
choose 2 path=[1,2] used=[T,T,F]
choose 3 path=[1,2,3] used=[T,T,T] -> COLLECT!
undo 3 path=[1,2] used=[T,T,F]
undo 2 path=[1] used=[T,F,F]
choose 3 path=[1,3] used=[T,F,T]
choose 2 path=[1,3,2] used=[T,T,T] -> COLLECT!
... continues for [2,...] and [3,...] branches
Step 04

Edge Cases

Single element
[1] -> [[1]] — one permutation. The recursion immediately hits the base case.
Two elements
[1,2] -> [[1,2],[2,1]] — 2! = 2 permutations. The simplest case that exercises all parts of the algorithm.
Negative numbers
[-1,0,1] — works exactly the same. The algorithm doesn't depend on element values, only their positions and uniqueness.
All elements are distinct (guaranteed)
The problem guarantees distinct integers. For duplicates, you'd need Permutations II (#47) with sorting and skip logic.
Step 05

Full Annotated Code

class Solution {

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

    private void backtrack(int[] nums, boolean[] used,
                           List<Integer> path,
                           List<List<Integer>> result) {

        // Base case: all positions filled
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path)); // copy!
            return;
        }

        // Try each unused element
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;       // skip used

            // Choose
            used[i] = true;
            path.add(nums[i]);

            // Explore
            backtrack(nums, used, path, result);

            // Unchoose (backtrack)
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}
Step 06

Interactive Demo

Enter distinct integers and watch the backtracking algorithm build permutations step by step through the decision tree.

Backtracking Visualizer


Step 07

Complexity Analysis

Time
O(n! * n)
Space
O(n)

We generate all n! permutations, and copying each one into the result takes O(n). The recursion stack and used array use O(n) space (not counting the output).

📝

This is optimal for generating permutations. Since there are n! permutations and we must output each one (of length n), no algorithm can do better than O(n! * n). The backtracking approach achieves this bound with minimal overhead.