#46 Permutations
frequently reported atLinkedInAmazonMicrosoftBloombergGoogleMeta
the problem
In plain words
Given an array of distinct integers, return all possible orderings (permutations), in any order.
in nums = [1,2,3]
out [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
in nums = [0,1]
out [[0,1],[1,0]]
in nums = [1]
out [[1]]
- 1 ≤ nums.length ≤ 6
- -10 ≤ nums[i] ≤ 10
- All values are distinct
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBacktracking: permutations
Fill positions left to right. Any element not used yet may go in the next position — a used[] array tells you which.
solutions
From brute force to optimal
Build permutations of the first k numbers, then insert number k+1 into every gap of each.
- Start with [[]].
- For each x, for each permutation p, insert x at positions 0 … p.size().
- Replace the list with the new one.
n! final permutations, each built by an O(n) copy-and-insert.
Holds a whole generation of permutations at once.
class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> result = new ArrayList<>(); result.add(new ArrayList<>()); for (int x : nums) { List<List<Integer>> next = new ArrayList<>(); for (List<Integer> p : result) { for (int pos = 0; pos <= p.size(); pos++) { // every gap, including both ends List<Integer> q = new ArrayList<>(p); q.add(pos, x); next.add(q); } } result = next; } return result; }}At each depth loop over all indices, skip used ones, choose, recurse, un-choose.
- If path has n elements, record a copy.
- For i in 0..n−1: skip if used[i].
- used[i] = true; path.add; recurse; path.remove; used[i] = false.
n! leaves, each copied in O(n); internal nodes add only a constant factor (≈ e·n! nodes).
used[], path and recursion depth (excluding output).
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) { 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; } }}Dry run
Position first takes each element from first onward by swapping it in; recurse on first + 1; swap back.
- If first == n, record nums as a list.
- For i from first: swap(first, i), recurse(first + 1), swap(first, i).
Same tree shape; still O(n) to copy each permutation.
No used[] or path — the array itself is the state.
class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> result = new ArrayList<>(); backtrack(nums, 0, result); return result; } private void backtrack(int[] nums, int first, List<List<Integer>> result) { if (first == nums.length) { List<Integer> perm = new ArrayList<>(); for (int x : nums) perm.add(x); result.add(perm); return; } for (int i = first; i < nums.length; i++) { swap(nums, first, i); // choose: nums[i] takes position `first` backtrack(nums, first + 1, result); // explore the rest swap(nums, first, i); // un-choose: put it back } } private static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }}in the room
How to say it in the interview
talk track
- "There are n! answers, each of length n, so O(n·n!) is the floor."
- Contrast with subsets: loop from 0 (order matters) and use
used[]instead ofstart. - Mention the swap trick as the O(1)-extra-state variant — but note it doesn't produce lexicographic order.
traps
- Resetting
used[i]but forgettingpath.remove, or vice versa. - Starting the loop at
start(that generates combinations, not permutations).
what they ask next
Follow-ups
Duplicates in nums (LC 47 Permutations II)?
Sort; skip i when nums[i] == nums[i-1] && !used[i-1].
Only the next permutation (LC 31)?
No backtracking needed: find the rightmost ascent, swap with the next larger element to its right, reverse the suffix — O(n).
before you submit
Edge cases to test
- One number → [[x]].
- Six numbers → 6! = 720 permutations, the maximum.
- Negative numbers and 0 behave like any other value.
practise next
Similar problems
- #78SubsetsMediumin Backtracking
- #31Next PermutationMediumin Arrays & Strings
- #51N-QueensHardin Backtracking