Permutations (LC 46)

Pattern: Backtracking
Difficulty: Medium
Key Concept: Build every ordering of distinct elements by fixing one position at a time and exploring choices, then undo (backtrack).

Problem Statement

Given an array nums of distinct integers, return all possible permutations of those numbers. The order of permutations in the output list does not matter, but each permutation must be a complete rearrangement of nums.

Input

nums: int[] — length n, all values distinct (typical constraint: 1 <= n <= 6 on LeetCode).

Output

List<List<Integer>> — every distinct ordering of the elements of nums.

Example

nums = [1, 2, 3]
Output includes [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] (6 permutations).

1. Algorithm & Pseudocode

Brute force (conceptual)

Conceptually: enumerate all n! full arrangements
Filter duplicates — not needed when all nums are distinct
Return as List<List<Integer>>

Optimal — visited-array backtracking

result = empty
path = empty list
used = boolean[n], all false

backtrack():
    if path.size() == n:
        result.add(copy of path)
        return
    for i = 0 .. n-1:
        if used[i]: continue
        used[i] = true
        path.add(nums[i])
        backtrack()
        path.remove last element
        used[i] = false

Optimal — swap-based backtracking

result = empty
working = copy of nums (mutable list)

backtrack(start):
    if start == n:
        result.add(copy of working)
        return
    for i = start .. n-1:
        swap(working[start], working[i])
        backtrack(start + 1)
        swap(working[start], working[i])   // undo

2. Step-by-Step Analysis (Beginner-Friendly)

Why backtracking? A permutation is a sequence of n choices. After you try putting nums[i] in the next slot, you must undo that choice so you can try another index. Without undo, you would only explore one path.
Visited array — nums stays fixed. used[i] means “index i is already in path.” Clear and matches how humans mark “already picked.”
Swap method — The prefix working[0 .. start-1] is fixed; the suffix is permuted by swapping into position start. The second swap restores the array so the parent call can try the next i.
Why new ArrayList<>(path)? path (or working) is reused. Adding the same list reference to result would make every “answer” point at one list that keeps changing. Copying freezes the answer at the leaf.
Why remove from the end? path.remove(path.size() - 1) is O(1) amortized for ArrayList. Removing from the middle is O(n).

3. The Dry Run

Sample: nums = [1, 2, 3] — visited-array DFS (try smaller index first).

Notation: path = current list, used = booleans for indices 0,1,2.

Step	Event	`path`	`used` (0,1,2)
1	Enter, pick i=0	`[1]`	T, F, F
2	Recurse, pick i=1	`[1,2]`	T, T, F
3	Recurse, pick i=2	`[1,2,3]`	T, T, T
4	Full length → add `[1,2,3]`, backtrack	`[1,2]`	T, T, F
5	Backtrack to `[1]`, pick i=2	`[1,3]`	T, F, T
6	Pick i=1	`[1,3,2]`	T, T, T
7	Add `[1,3,2]`, unwind further	—	—

Decision tree (all 6 leaves)

                         []
            /            |            \
         [1]            [2]            [3]
       /    \         /    \         /    \
   [1,2] [1,3]   [2,1] [2,3]   [3,1] [3,2]
     |     |       |     |       |     |
 [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]

Swap-based trace (abbreviated): working = [1,2,3]. At start=0: swap (0,0), recurse; swap (0,1) → [2,1,3], recurse; swap back; swap (0,2) → [3,2,1], recurse; swap back. Recursion fills start=1,2 similarly.

4. Java Solution

Brute Force

Conceptually generate all n! orderings (same asymptotic cost as structured backtracking; “brute” here means the unstructured mental model). A direct recursive generator still mirrors swap-backtracking.

Time: O(n! · n) — n! permutations, each length n to copy.
Space: O(n) recursion stack plus output.

import java.util.*;

class SolutionBrute {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        for (int x : nums) cur.add(x);
        permuteAll(cur, 0, result);
        return result;
    }

    private void permuteAll(List<Integer> cur, int start, List<List<Integer>> result) {
        if (start == cur.size()) {
            result.add(new ArrayList<>(cur));
            return;
        }
        for (int i = start; i < cur.size(); i++) {
            Collections.swap(cur, start, i);
            permuteAll(cur, start + 1, result);
            Collections.swap(cur, start, i);
        }
    }
}

Optimal

A) Visited boolean array

import java.util.*;

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

    private void backtrack(int[] nums, boolean[] used, List<Integer> path, 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, used, path, result);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

B) Swap-based (working list)

import java.util.*;

class SolutionSwap {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> working = new ArrayList<>();
        for (int x : nums) working.add(x);
        backtrack(working, 0, result);
        return result;
    }

    private void backtrack(List<Integer> working, int start, List<List<Integer>> result) {
        if (start == working.size()) {
            result.add(new ArrayList<>(working));
            return;
        }
        for (int i = start; i < working.size(); i++) {
            Collections.swap(working, start, i);
            backtrack(working, start + 1, result);
            Collections.swap(working, start, i);
        }
    }
}

5. The “Java vs. Others” Edge

new ArrayList<>(current) copies the list so each answer is independent. Never result.add(path) while path is still mutating.
path.remove(path.size() - 1) — O(1) pop from end. C++: pop_back(). Python: path.pop().
List<List<Integer>> — outer list holds references; each inner list must be a new ArrayList when stored.
Collections.swap(list, i, j) — idiomatic in-place swap for List; C++ often uses std::swap.

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n! · n)	O(n) stack + output	Same order as structured backtracking; contrasts conceptual “try everything” vs explicit undo
Optimal (visited)	O(n! · n)	O(n) for `used`, `path`, stack + output	Copy length-n list at each leaf
Optimal (swap)	O(n! · n)	O(n) stack + working list + output	No `used[]`; restore with swap

Output size is Θ(n · n!); no algorithm can use o(n!) time for this problem.