Difficulty: MediumBacktracking

Permutations

Problem in Plain English

Given distinct integers, return every possible ordering that uses each element exactly once. All orderings are collected and their sequence does not matter.

Problem Statement

Given an array nums of distinct integers, return every possible ordering of all its elements.

Each ordering must use every element exactly once, so an ordering is a rearrangement of the full array, not a shorter selection.

Return the full list in any order.

Constraints

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.

Examples

Example 1

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

There are three choices for the first slot, two for the next, and one for the last: six orderings. Each contains 1, 2, and 3 once. Changing their positions creates a distinct answer.

Example 2

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Zero is an ordinary value, not an unused marker. Either 0 or 1 comes first and the other must follow, giving exactly two answers.

Example 3

Input: nums = [1]
Output: [[1]]

The only slot must contain 1. The result still has an outer list of answers and an inner one-element ordering.

Intuition

An ordering chooses who occupies each slot, so [1,2,3] and [1,3,2] are different answers. The challenge is using every input exactly once. A baseline fills slots freely and rejects repeats at the end; swapping instead keeps used values in a fixed prefix and remaining values in a suffix. Backtracking restores each swap before trying another candidate, so one branch cannot corrupt the next.

Approaches

Unguided Guessing

Solution Details

Reveal Unguided Guessing: intuition, complexity, and code

Intuition

Fill the n positions one by one, trying every array value in each slot with no memory of earlier picks. Finished rows that repeat a value are thrown away, so only genuinely fresh orderings survive the filter.

Step-by-Step Logic

Begin with an empty row. Until it contains n values, try every input value as the next value, recurse, then pop. In Example 1 the first subtree begins with [1].
At length n, construct a set of the row values. Accept only when its size is n, and copy the row before returning. In Example 1 [1,1,1], [1,1,2], and [1,1,3] fail.
Continue all siblings and root choices. [1,2,3] and [1,3,2] pass; the first value 2 gives [2,1,3] and [2,3,1], and first value 3 gives [3,1,2] and [3,2,1].
Return the six saved rows after all 27 length-three rows have been checked. The temporary row is empty again and the input array has never changed.

Why It Works

Choosing every input value at each of n slots visits every length-n row over the input, including each valid permutation. Because inputs are distinct, a row of length n with n distinct values contains exactly all input values once. The set-size check therefore accepts precisely the valid permutations. Each row has a unique choice sequence and is visited once. Copying accepted rows preserves them while pop restores the parent row.

Dry Run

Unguided Guessing: variable states at each step
row on call entry	length / set size at leaf	action	accepted rows so far
[]	0 / not checked	try 1, 2, 3 in order; pop after every child	[]
[1]	1 / not checked	try 1, 2, 3 in order; pop after every child	[]
[1,1]	2 / not checked	try 1, 2, 3 in order; pop after every child	[]
[1,1,1]	3 / 1	reject repeat; return then parent pops	[]
[1,1,2]	3 / 2	reject repeat; return then parent pops	[]
[1,1,3]	3 / 2	reject repeat; return then parent pops	[]
[1,2]	2 / not checked	try 1, 2, 3 in order; pop after every child	[]
[1,2,1]	3 / 2	reject repeat; return then parent pops	[]
[1,2,2]	3 / 2	reject repeat; return then parent pops	[]
[1,2,3]	3 / 3	copy and record; return then parent pops	[[1,2,3]]
[1,3]	2 / not checked	try 1, 2, 3 in order; pop after every child	[[1,2,3]]
[1,3,1]	3 / 2	reject repeat; return then parent pops	[[1,2,3]]
[1,3,2]	3 / 3	copy and record; return then parent pops	[[1,2,3],[1,3,2]]
[1,3,3]	3 / 2	reject repeat; return then parent pops	[[1,2,3],[1,3,2]]
[2]	1 / not checked	try 1, 2, 3 in order; pop after every child	[[1,2,3],[1,3,2]]
[2,1]	2 / not checked	try 1, 2, 3 in order; pop after every child	[[1,2,3],[1,3,2]]
[2,1,1]	3 / 2	reject repeat; return then parent pops	[[1,2,3],[1,3,2]]
[2,1,2]	3 / 2	reject repeat; return then parent pops	[[1,2,3],[1,3,2]]
[2,1,3]	3 / 3	copy and record; return then parent pops	[[1,2,3],[1,3,2],[2,1,3]]
[2,2]	2 / not checked	try 1, 2, 3 in order; pop after every child	[[1,2,3],[1,3,2],[2,1,3]]
[2,2,1]	3 / 2	reject repeat; return then parent pops	[[1,2,3],[1,3,2],[2,1,3]]
[2,2,2]	3 / 1	reject repeat; return then parent pops	[[1,2,3],[1,3,2],[2,1,3]]
[2,2,3]	3 / 2	reject repeat; return then parent pops	[[1,2,3],[1,3,2],[2,1,3]]
[2,3]	2 / not checked	try 1, 2, 3 in order; pop after every child	[[1,2,3],[1,3,2],[2,1,3]]
[2,3,1]	3 / 3	copy and record; return then parent pops	[[1,2,3],[1,3,2],[2,1,3],[2,3,1]]
[2,3,2]	3 / 2	reject repeat; return then parent pops	[[1,2,3],[1,3,2],[2,1,3],[2,3,1]]
[2,3,3]	3 / 2	reject repeat; return then parent pops	[[1,2,3],[1,3,2],[2,1,3],[2,3,1]]
[3]	1 / not checked	try 1, 2, 3 in order; pop after every child	[[1,2,3],[1,3,2],[2,1,3],[2,3,1]]
[3,1]	2 / not checked	try 1, 2, 3 in order; pop after every child	[[1,2,3],[1,3,2],[2,1,3],[2,3,1]]
[3,1,1]	3 / 2	reject repeat; return then parent pops	[[1,2,3],[1,3,2],[2,1,3],[2,3,1]]
[3,1,2]	3 / 3	copy and record; return then parent pops	[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2]]
[3,1,3]	3 / 2	reject repeat; return then parent pops	[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2]]
[3,2]	2 / not checked	try 1, 2, 3 in order; pop after every child	[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2]]
[3,2,1]	3 / 3	copy and record; return then parent pops	[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
[3,2,2]	3 / 2	reject repeat; return then parent pops	[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
[3,2,3]	3 / 2	reject repeat; return then parent pops	[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
[3,3]	2 / not checked	try 1, 2, 3 in order; pop after every child	[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
[3,3,1]	3 / 2	reject repeat; return then parent pops	[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
[3,3,2]	3 / 2	reject repeat; return then parent pops	[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
[3,3,3]	3 / 1	reject repeat; return then parent pops	[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
[] restored	0	root finished; return	[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Complexity Analysis

Time Complexity

O(n \cdot n^n)

Space Complexity

O(n \cdot n!)

For n distinct values there are n^n completed rows. Every leaf builds a set by scanning n values (expected linear work), and accepted rows are copied at length n. The recursion tree adds O(n^n) calls for n >= 2. Stack, current row and temporary set use O(n) auxiliary space. Returning all n! lists uses O(n times n!) total space, which dominates; n = 1 is constant. Do not omit the leaf-validation factor n or the saved answers.

Code

Solution.java

1import java.util.*;2
3class Solution {4    public List<List<Integer>> permute(int[] nums) {5        List<List<Integer>> res = new ArrayList<>();6        dfs(nums, new ArrayList<>(), res);7        return res;8    }9
10    private void dfs(int[] nums, List<Integer> row, List<List<Integer>> res) {11        if (row.size() == nums.length) {12            // Length n with n distinct values must use every input once.13            if (new HashSet<>(row).size() == nums.length) {14                res.add(new ArrayList<>(row));15            }16            return;17        }18        for (int v : nums) {19            row.add(v);20            dfs(nums, row, res);21            row.remove(row.size() - 1);22        }23    }24}

Hints

Hint 1

Each answer uses every element exactly once, so every recursion level can fix one more position.

Hint 2

Track which elements are already placed, either with a used array or by swapping placed elements to the front.

Hint 3

Swap a candidate into the current slot, recurse to the next slot, then swap back so sibling branches start clean.

Edge Cases

A single element [1] has exactly one ordering, [[1]], with no swaps needed.
Two elements [0, 1] give [[0, 1], [1, 0]], the smallest case that actually branches.
Negative numbers and zero permute exactly like positives because only positions matter, never values.

Common Mistakes and Interview Tips

Forgetting to swap back after recursing, which hands the next sibling a scrambled array and fabricates orderings.
Recording the live array instead of a copy, so every stored answer ends up identical to the final state.
Stopping the loop at the current slot instead of scanning the whole tail, which strands unplaced elements and loses orderings.
Calling the swap approach constant-space without counting its recursion stack or the n! copied output rows.

Key Takeaway

Ordering problems are slot-filling walks: fix one position per level from the still-unused pool and undo the choice on the way back up.