LeetCode · #46

Permutations Solution

Given an array of distinct integers, return all possible permutations. Each element must appear exactly once in every permutation.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #46

🏗️

Pattern

Backtracking — permutation with used-array

Given an array nums of distinct integers, return all the possible permutations in any order. For n elements, there are exactly n! permutations.

Example

 Input: nums = [1, 2, 3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
// 3! = 6 permutations 

Constraints

 • 1 ≤ nums.length ≤ 6  ← at most 6! = 720 permutations • -10 ≤ nums[i] ≤ 10 • All integers of nums are unique 

Section Two · Approach 1

Swap-based In-place — O(n · n!)

Fix one element at position 0 by swapping it with each element in turn, then recursively permute the rest of the array. After recursion, swap back (backtrack) to restore the original order. The result is collected when the recursion depth equals n.

Why it works

Every permutation can be constructed by choosing which element appears first, then permuting the rest. The swap-then-recurse approach systematically places each possible element at the front, then restores the array state after exploring that branch.

Why we can do better (readability)

Problem: The swap method mutates the input array, making the code subtle — you must remember to swap back. The used-array approach builds a fresh path list, never touches the input, and clearly mirrors the choose/unchoose pattern used for subsets and combinations, making it easier to adapt to variants with duplicates (LC 47).

Java — Swap-based (in-place)

 import java.util.*;
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
swap(nums, 0, res);
return res;
    }
private void swap(int[] nums, int start, List<List<Integer>> res) {
if (start == nums.length) {
List<Integer> perm = new ArrayList<>();
for (int n : nums) perm.add(n);
            res.add(perm);
return;
        }
for (int i = start; i < nums.length; i++) {
swapArr(nums, start, i); // choose: bring element i to front swap(nums, start + 1, res);
swapArr(nums, start, i); // unchoose: restore original order
}
    }
private void swapArr(int[] a, int i, int j) {
int t = a[i]; a[i] = a[j]; a[j] = t;
    }
}

Python — Swap-based (in-place)

 class Solution:
def permute(self, nums: list[int]) -> list[list[int]]:
        res = []
def bt(start: int) -> None:
if start == len(nums):
                res.append(nums[:])
return for i in range(start, len(nums)):
                nums[start], nums[i] = nums[i], nums[start] # choose bt(start + 1)
                nums[start], nums[i] = nums[i], nums[start] # unchoose bt(0)
return res

Metric	Value
Time	O(n · n!) — n! permutations, O(n) to copy each
Space	O(n) call stack (excluding output)

Section Three · Approach 2

Backtracking with Used-Array — O(n · n!)

Maintain a boolean used[] array to track which elements are already in the current path. At each position, try every unused element, add it, recurse to the next position, then remove it and mark it unused.

💡 Mental model: Imagine assigning seats at a dinner table. You have n guests and n chairs. You seat guest 1 in chair 1, then decide who sits in chair 2 (anyone not yet seated), and so on. When you've filled all chairs, record the seating arrangement. Then un-seat the last guest, try another guest in that chair, and continue. The "seating chart clipboard" is the used[] array — you mark off a guest when they sit down and erase the mark when they stand up.

Algorithm — used-array backtracking

State: path (current permutation being built), used[] (which elements are in path).
Base case: path.size() == n → add copy of path to result.
Loop: for each index i in nums: if used[i] is false, mark used, add to path, recurse, remove from path, mark unused.
No start index needed — unlike combinations, permutations consider all elements at every level.

🎯 When to recognize this pattern:

"All possible orderings / arrangements of distinct elements." Permutation problems don't have a start-index constraint (every unused element is fair game at each level), which distinguishes them from combination problems.
This template extends directly to LC 47 (Permutations II, with duplicates — add a sort + skip-duplicates guard).

Why not use a HashSet instead of boolean array?:

For small n (≤ 6 per constraints), a boolean array indexed by position is O(1) and cache-friendly.
A HashSet has higher constant factor overhead.
If the values were large integers, a set would be needed — but since indices 0..n−1 are bounded, the array wins.

Section Four · Trace

Visual Walkthrough

Trace for nums = [1, 2, 3]. Each level picks one unused element. The full tree has 6 leaves (3! = 6).

Permutations — Backtracking Tree (nums = [1, 2, 3])

Section Five · Implementation

Code — Java & Python

Java — Backtracking with used-array

 import java.util.*;
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrack(nums, new boolean[nums.length], new ArrayList<>(), res);
return res;
    }
private void backtrack(int[] nums, boolean[] used,
List<Integer> path,
List<List<Integer>> res) {
if (path.size() == nums.length) {
            res.add(new ArrayList<>(path)); // snapshot — path is reused return;
        }
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue; // already in current permutation
used[i] = true;
            path.add(nums[i]);
backtrack(nums, used, path, res);
            path.remove(path.size() - 1); // backtrack
used[i] = false; // backtrack
}
    }
}

Python — Backtracking with used-array

 class Solution:
def permute(self, nums: list[int]) -> list[list[int]]:
        res, path = [], []
        used = [False] * len(nums)
def backtrack() -> None:
if len(path) == len(nums):
                res.append(path[:]) # snapshot return for i in range(len(nums)):
if used[i]:
continue # skip elements already chosen
used[i] = True
path.append(nums[i])
backtrack()
                path.pop() # backtrack
used[i] = False # backtrack backtrack()
return res

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Iterative (insert into positions)	O(n · n!)	O(n · n!)	No recursion overhead but harder to extend to duplicate handling
Swap-based backtracking	O(n · n!)	O(n)	Mutates input; subtle to debug
Used-array backtracking ← optimal	O(n · n!)	O(n)	Clean, non-mutating, trivially extensible to LC 47 (duplicates)

Why n · n! and not just n!?:

There are n! permutations and for each one we copy the path (O(n)) to the result list.
Nodes in the backtracking tree: n! leaves + internal nodes (roughly e · n! ≈ 2.7 · n!).
Total work is bounded by O(n · n!) despite the internal node overhead.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Single element	`[42]`	Only one permutation: `[[42]]`. Base case fires immediately.
Two elements	`[1, 2]`	Two permutations: `[[1,2],[2,1]]`. Smallest non-trivial case.
Negative numbers	`[-1, 0, 1]`	No comparison used — used[] tracks indices, not values. Works correctly.
Max input n=6	6 elements	6! = 720 permutations. Call stack depth = 6. Well within limits.
Forgetting to unset used[i]	any	Not backtracking `used[i] = false` makes all future branches think the element is still used. Zero permutations after the first.
Storing reference instead of copy	any	`res.add(path)` leads to all results being the same (empty) list at the end.

⚠ Common Mistake: Forgetting to reset used[i] = false after the recursive call. The used[] array is shared across all levels of recursion. If you don't unset it, once an element is used on any path, it stays "used" for all future paths. Every permutation after the first will be missing that element. The backtrack and the mark/unmark must always appear as a matched pair.

← Back to Backtracking problems

LearningTree

LC 46 · Permutations — Solution & Explanation | DSA Guide