Generate All Permutations Using Backtracking
Fast recall
Quick revision
Core answer
n, record a copy. There are n! permutations, each length n, so O(n * n!) total. The choose/recurse/un-choose pattern with a used marker prevents reusing an element within one permutation.Whether you avoid reusing elements via a used[] flag (or swap) and snapshot on completion
Reusing the same element in a permutation, or adding the mutable list reference
Mention the in-place swap variant and handling duplicates by sorting + skipping
Interview-ready guide
Interview answer
A permutation is an arrangement that uses every element exactly once, and there are n factorial of them.
I generate them all with backtracking, building one permutation position by position. At each position, I try placing every element that hasn't already been used in the current permutation. To track that, I keep a boolean used array, where used at index i tells me whether the i-th element is already in my current path.
So in the loop, if an element is used, I skip it; otherwise I mark it used and add it to the path, that's the choose step, recurse to fill the next position, and then when the recursion returns I unmark it and remove it from the path, the un-choose step. When my path reaches length n, I've built a complete permutation, so I record a copy of it.
The total work is O of n times n factorial, since there are n factorial permutations and copying each one costs n. There's also an alternative in-place swap approach, where instead of a used array I swap the current index with each of the later indices, which generates permutations by rearranging the array itself; it saves the extra array but mutates the input.
The two mistakes to avoid are reusing an element within a single permutation, which the used array prevents, and adding the live path list instead of a copy when recording a result.
If the input contains duplicate values and I want only distinct permutations, I sort the array first and skip an element when it equals the previous element and that previous element hasn't been used at this level, which avoids generating duplicate arrangements.
Generate All Permutations Using Backtracking
Direct Answer
Build each permutation by picking an unused element at every position and recursing. Track used elements with a boolean[] used (or swap in place). When the path length equals n, record a copy. There are n! permutations, each length n, so O(n * n!) total. The choose/recurse/un-choose pattern with a used marker prevents reusing an element within one permutation.
Deep Dive & Architecture
A permutation fills the result from left to right. At each position, choose any input value that has not already been used, recurse for the next position, then undo the choice.
Worked example: [1, 2, 3]
Choose 1, then 2, then 3 to record [1, 2, 3]. Remove 3 and 2, choose 3 after 1, then choose 2 to record [1, 3, 2]. Backtracking to the empty path lets 2 and then 3 become the first value. All six orders are eventually produced.
A boolean[] used makes membership checks O(1). The invariant is that the path contains no input index twice. At path length n, copy it into the result. An alternative swaps candidates into the current position in the same array; that avoids used but requires each swap to be undone correctly.
There are n! outputs for distinct values, and copying each length-n permutation gives O(n × n!) work. The recursion path and used array take O(n) extra space, excluding the output.
If values repeat and only unique permutations are wanted, sort the input and skip an equal value when its identical predecessor has not been used in the current branch.
Code Example
List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrack(nums, new boolean[nums.length], new ArrayList<>(), res);
return res;
}
void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue; // skip already-used element
used[i] = true; path.add(nums[i]); // choose
backtrack(nums, used, path, res); // explore
used[i] = false; path.remove(path.size() - 1); // un-choose
}
}
// nums = {1,2,3} -> 123,132,213,231,312,321 (3! = 6)
Common Mistakes & Pitfalls
- Reusing an element: without
used[](or swapping), you get invalid repeats like [1,1,2]. - Adding the reference: snapshot the path on completion, don't add the live list.
- Forgetting to reset
used[i]: must clear it during un-choose. - Duplicates producing repeats: sort and skip
nums[i] == nums[i-1] && !used[i-1].
Check your understanding
Answer these without looking back at the article.
- What is backtracking and how does it differ from regular recursion?
- How do you generate all subsets of a set using backtracking?
- How do you find all combinations that sum to a target?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.