Permutations (LeetCode
Learn how to solve the Permutations problem using backtracking, recursion, visited arrays, decision trees, and in-place swapping. Includes intuition, dry runs, Java code, complexity analysis, interview tips, and production applications.
Introduction
Permutations is one of the most important backtracking interview problems.
It is frequently asked by companies such as:
- Amazon
- Microsoft
- Meta
- Apple
- Adobe
- Bloomberg
- Goldman Sachs
- JPMorgan Chase
This problem teaches how to:
- Explore every possible ordering
- Build solutions one position at a time
- Track used elements
- Restore state after recursion
- Understand factorial time complexity
- Handle duplicate values correctly
- Compare visited-array and in-place swapping approaches
Permutations are closely related to:
- Subsets
- Combinations
- Combination Sum
- N-Queens
- Sudoku Solver
- Word Search
- String rearrangement problems
- Scheduling and assignment problems
The fundamental backtracking pattern remains:
graph TD
Choose["Choose"] --> Explore["Explore"]
Explore["Explore"] --> Unchoose["Unchoose"]
Problem Statement
Given an integer array nums containing distinct integers, return all possible permutations.
The answer may be returned in any order.
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]
]
Example 2
Input
nums = [0,1]
Output
[
[0,1],
[1,0]
]
Example 3
Input
nums = [1]
Output
[
[1]
]
What Is a Permutation?
A permutation is an arrangement of all elements in a particular order.
For:
[1,2,3]
valid permutations include:
[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]
Unlike subsets, order matters.
[1,2,3]
and:
[2,1,3]
are different permutations.
Permutation vs Combination vs Subset
| Concept | Order Matters? | Uses All Elements? |
|---|---|---|
| Permutation | Yes | Usually yes |
| Combination | No | Selects a fixed number |
| Subset | No | Selects zero or more |
Example using:
[1,2,3]
Permutation:
[1,2,3]
[2,1,3]
These are different because order matters.
Combination:
[1,2]
and:
[2,1]
represent the same selection.
How Many Permutations Exist?
For n unique elements, the number of permutations is:
n!
Factorial means:
n!
=
n × (n - 1) × (n - 2) × ... × 1
Examples:
| Elements | Number of Permutations |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 6 |
| 4 | 24 |
| 5 | 120 |
| 6 | 720 |
| 10 | 3,628,800 |
Permutation generation grows very quickly.
Why Are There n! Permutations?
For the first position, we have:
n choices
After selecting one element, the second position has:
n - 1 choices
The third position has:
n - 2 choices
Therefore:
n × (n - 1) × (n - 2) × ... × 1
=
n!
For three elements:
3 × 2 × 1
=
6
Decision Tree Intuition
For:
nums = [1,2,3]
the first position can contain any of the three numbers.
graph TD
N_1_0_0["1"] --> N_1_1_1["1"]
N_1_0_0["1"] --> N_2_1_2["2"]
N_2_0_1["2"] --> N_1_1_3["1"]
N_2_0_1["2"] --> N_3_1_4["3"]
N_3_0_2["3"] --> N_2_1_5["2"]
N_3_0_2["3"] --> N_1_1_6["1"]
N_1_1_1["1"] --> N_1_2_1["1"]
N_1_1_1["1"] --> N_2_2_2["2"]
N_2_1_2["2"] --> N_3_2_3["3"]
N_2_1_2["2"] --> N_1_2_4["1"]
N_1_2_1["1"] --> N_3_2_5["3"]
N_1_2_1["1"] --> N_2_2_6["2"]
N_3_1_4["3"] --> N_2_2_7["2"]
N_3_1_4["3"] --> N_1_2_8["1"]
N_2_1_5["2"] --> N_3_2_9["3"]
N_2_1_5["2"] --> N_2_2_10["2"]
N_1_1_6["1"] --> N_3_2_11["3"]
N_1_1_6["1"] --> N_1_2_12["1"]
N_2_1_6["2"] --> N_3_2_13["3"]
N_2_1_6["2"] --> N_1_2_14["1"]
N_3_1_7["3"] --> N_2_2_15["2"]
N_3_1_7["3"] --> N_3_2_16["3"]
N_3_1_8["3"] --> N_2_2_17["2"]
N_3_1_8["3"] --> N_1_2_18["1"]
Each recursion level fills one position.
Backtracking State
For this problem, the state includes:
Current permutation
Used elements
Current depth
At each recursion level:
- Try every unused element.
- Add it to the current permutation.
- Mark it as used.
- Recurse.
- Remove it.
- Mark it as unused.
Generic Backtracking Template
void backtrack(State state) {
if (solutionComplete) {
saveSolution();
return;
}
for (Choice choice : choices) {
if (choiceIsInvalid) {
continue;
}
choose(choice);
backtrack(updatedState);
unchoose(choice);
}
}
For permutations:
Choice
Any unused element
Base Condition
Current size equals input length
Choose
Add element and mark used
Unchoose
Remove element and mark unused
Approach 1 — Backtracking with a Visited Array
Core Idea
Use a boolean array to track which elements are already part of the current permutation.
Example:
nums = [1,2,3]
used = [true,false,true]
This means:
1 is used
2 is available
3 is used
At every recursion level, loop through the complete input array and choose only unused elements.
Algorithm
graph TD
Start_with_Empty_Path["Start with Empty Path"] --> Current_Path_Size_nums_lengt["Current Path Size == nums.length?"]
Current_Path_Size_nums_lengt["Current Path Size == nums.length?"] --> Element_Already_Used["Element Already Used?"]
Element_Already_Used["Element Already Used?"] --> Mark_Used["Mark Used"]
Mark_Used["Mark Used"] --> Recurse["Recurse"]
Recurse["Recurse"] --> Remove_Element["Remove Element"]
Remove_Element["Remove Element"] --> Mark_Unused["Mark Unused"]
Java Code — Visited Array
import java.util.ArrayList;
import java.util.List;
public class Permutations {
public List<List<Integer>> permute(
int[] nums) {
List<List<Integer>> result =
new ArrayList<>();
boolean[] used =
new boolean[nums.length];
backtrack(
nums,
used,
new ArrayList<>(),
result);
return result;
}
private void backtrack(
int[] nums,
boolean[] used,
List<Integer> current,
List<List<Integer>> result) {
if (current.size() == nums.length) {
result.add(
new ArrayList<>(current));
return;
}
for (int i = 0;
i < nums.length;
i++) {
if (used[i]) {
continue;
}
used[i] = true;
current.add(nums[i]);
backtrack(
nums,
used,
current,
result);
current.remove(
current.size() - 1);
used[i] = false;
}
}
}
Choose–Explore–Unchoose Breakdown
Choose
used[i] = true;
current.add(nums[i]);
The current element is selected.
Explore
backtrack(
nums,
used,
current,
result);
Continue building the next position.
Unchoose
current.remove(
current.size() - 1);
used[i] = false;
Restore the state so another branch can use the element.
Why Loop from Index 0 Every Time?
For subsets, recursion usually starts from:
i + 1
because order does not matter and elements should only move forward.
For permutations, every unused element may be selected for the next position.
Therefore, the loop always starts from:
0
Example:
After choosing 2, the next valid element may be 1.
[2,1,3]
If we only moved forward through indexes, this permutation would never be generated.
Why Do We Need the Used Array?
The used array prevents choosing the same input element more than once in the same permutation.
Without it, we could generate invalid results such as:
[1,1,1]
[2,2,3]
[3,3,3]
The array tracks usage by index rather than value.
Why Track by Index?
Suppose the array contains duplicate values:
[1,1,2]
The two 1 values are different input positions.
Tracking only by value would not distinguish them.
For LeetCode #46, all values are unique, but index-based tracking is still the standard approach.
Base Condition
A complete permutation contains every input element.
if (current.size() == nums.length)
At that point, save the result.
result.add(
new ArrayList<>(current));
Then return because no more elements can be added.
Why Must We Copy the Current List?
Correct:
result.add(
new ArrayList<>(current));
Incorrect:
result.add(current);
The current list is mutable and reused across all recursive branches.
If the same reference is stored, later backtracking changes every stored result.
Detailed Dry Run
Input:
nums = [1,2,3]
Initial state:
current = []
used = [false,false,false]
First Branch — Start with 1
Choose 1.
current = [1]
used = [true,false,false]
Recurse.
From [1], Choose 2
current = [1,2]
used = [true,true,false]
Recurse.
From [1,2], Choose 3
current = [1,2,3]
used = [true,true,true]
Current size equals input length.
Save:
[1,2,3]
Backtrack.
Remove 3.
current = [1,2]
used = [true,true,false]
No more unused elements.
Backtrack again.
Remove 2.
current = [1]
used = [true,false,false]
From [1], Choose 3
current = [1,3]
used = [true,false,true]
Recurse.
Choose 2.
current = [1,3,2]
used = [true,true,true]
Save:
[1,3,2]
Backtrack until:
current = []
used = [false,false,false]
Second Branch — Start with 2
Choose 2.
current = [2]
used = [false,true,false]
Possible continuations:
[2,1,3]
[2,3,1]
Both are saved.
Backtrack completely.
Third Branch — Start with 3
Choose 3.
current = [3]
used = [false,false,true]
Possible continuations:
[3,1,2]
[3,2,1]
Both are saved.
Final Result
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
Dry Run Table
| Depth | Current | Used | Action |
|---|---|---|---|
| 0 | [] |
[F,F,F] |
Choose 1 |
| 1 | [1] |
[T,F,F] |
Choose 2 |
| 2 | [1,2] |
[T,T,F] |
Choose 3 |
| 3 | [1,2,3] |
[T,T,T] |
Save |
| 2 | [1,2] |
[T,T,F] |
Remove 3 |
| 1 | [1] |
[T,F,F] |
Remove 2 |
| 1 | [1] |
[T,F,F] |
Choose 3 |
| 2 | [1,3] |
[T,F,T] |
Choose 2 |
| 3 | [1,3,2] |
[T,T,T] |
Save |
The same process continues for starting values 2 and 3.
Recursion Tree Size
At depth 0:
n choices
At depth 1:
n - 1 choices
At depth 2:
n - 2 choices
The total number of leaf nodes is:
n!
Time Complexity
There are:
n!
complete permutations.
Copying each permutation takes:
O(n)
Therefore, total output-generation time is:
O(n × n!)
The recursive search itself also visits intermediate states, but the dominant cost is generating and copying all complete permutations.
Space Complexity
Output Space
There are:
n!
permutations.
Each contains:
n
elements.
Therefore:
O(n × n!)
Recursion Stack
Maximum recursion depth:
O(n)
Auxiliary State
The used array requires:
O(n)
The current path also requires:
O(n)
Excluding output:
O(n)
Complexity Summary
| Complexity | Value |
|---|---|
| Time | O(n × n!) |
| Output Space | O(n × n!) |
| Auxiliary Space | O(n) |
| Recursion Depth | O(n) |
Why Is This Not O(n!) Only?
The algorithm produces n! permutations, but each complete permutation must be copied into the output.
Copying one permutation costs:
O(n)
Therefore:
O(n × n!)
is the more complete output-sensitive complexity.
Correctness Intuition
The algorithm is correct because:
- At each position, it tries every currently unused element.
- No element is used more than once in one path.
- A result is saved only after all elements are selected.
- Backtracking restores usage state for other branches.
- Every possible ordering corresponds to exactly one path in the recursion tree.
Therefore, all valid permutations are generated exactly once when the input values are unique.
Edge Cases
Empty Array
Mathematically, the empty set has one permutation:
[]
Depending on the platform specification, the result may be:
[[]]
The current implementation returns:
[[]]
because the base condition is true during the initial call.
Single Element
Input
[5]
Output:
[
[5]
]
Two Elements
Input
[1,2]
Output:
[
[1,2],
[2,1]
]
Negative Values
Input
[-1,2]
Output:
[
[-1,2],
[2,-1]
]
Common Interview Mistakes
Mistake 1 — Forgetting to Mark the Element as Used
Incorrect:
current.add(nums[i]);
backtrack(...);
Without marking the index, the same element may be reused repeatedly.
Mistake 2 — Forgetting to Unmark the Element
After recursion, this is required:
used[i] = false;
Otherwise, the element remains unavailable to sibling branches.
Mistake 3 — Forgetting to Remove the Last Element
This is required:
current.remove(
current.size() - 1);
Otherwise, values from previous branches remain in the path.
Mistake 4 — Looping from the Start Index
Unlike subsets, permutations must consider every unused element at every level.
Use:
for (int i = 0;
i < nums.length;
i++)
not a forward-only start index.
Mistake 5 — Saving the Same Mutable List
Incorrect:
result.add(current);
Correct:
result.add(
new ArrayList<>(current));
Mistake 6 — Using a Set Unnecessarily
For unique input values, the recursion already generates each permutation exactly once.
A Set<List<Integer>> adds hashing overhead and hides problems in the backtracking logic.
Mistake 7 — Incorrect Base Condition
Correct:
current.size() == nums.length
Saving at every recursion level would generate partial permutations rather than complete permutations.
Production Applications
Permutation generation appears in:
- Task ordering
- Job scheduling
- Route planning
- Test execution ordering
- Workflow sequencing
- Feature-priority analysis
- Tournament arrangements
- Resource assignment
- Dependency ordering experiments
- Cryptographic search spaces
Real-World Example — Test Execution Order
Suppose a test suite has three setup operations:
Load Data
Configure Cache
Start Service
Possible execution orders include:
Load Data → Configure Cache → Start Service
Load Data → Start Service → Configure Cache
Configure Cache → Load Data → Start Service
...
Generating permutations helps test whether ordering changes system behavior.
In production, constraints would normally prune invalid orders.
Real-World Example — Delivery Route Ordering
Suppose a driver must visit three locations:
A
B
C
Possible visit orders:
A → B → C
A → C → B
B → A → C
B → C → A
C → A → B
C → B → A
This is a permutation problem.
For many destinations, checking every permutation becomes impractical, so route-optimization algorithms and pruning techniques are required.
Backtracking vs Brute Force
Permutation generation is inherently exhaustive because all valid arrangements must be produced.
Backtracking improves the implementation by:
- Building one arrangement incrementally
- Reusing the current path
- Preventing invalid repeated usage
- Restoring state after each branch
- Supporting pruning in constrained variations
The total number of valid outputs remains factorial.
Interview Explanation
A strong interview explanation could be:
I build the permutation one position at a time. At each recursion level, I try every input element that has not already been used in the current path. I mark the element as used, add it to the path, recurse, and then remove it and mark it unused to restore the state. Once the path contains all
nelements, I copy it into the result. Since there aren!permutations and copying each one costs O(n), the total time complexity is O(n × n!).
Interview Tips
Interviewers commonly ask:
- Why does the loop start from zero each time?
- Why is a used array necessary?
- Why must state be restored?
- Why copy the current list?
- Why are there
n!permutations? - Why is the total time O(n × n!)?
- How would you handle duplicate values?
- Can the solution avoid the used array?
- Can permutations be generated in-place?
- Can results be generated lazily?
- How would you generate only the next permutation?
- What happens when
nbecomes large?
Explain the recursion tree and used-element tracking before writing code.
Unit Tests for the Visited-Array Solution
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;
import java.util.List;
import org.junit.jupiter.api.Test;
class PermutationsTest {
private final Permutations solution =
new Permutations();
@Test
void shouldGenerateAllPermutations() {
List<List<Integer>> result =
solution.permute(
new int[]{1, 2, 3});
assertEquals(
6,
result.size());
assertTrue(
result.contains(
List.of(1, 2, 3)));
assertTrue(
result.contains(
List.of(3, 2, 1)));
}
@Test
void shouldHandleTwoElements() {
List<List<Integer>> result =
solution.permute(
new int[]{0, 1});
assertEquals(
2,
result.size());
assertTrue(
result.contains(
List.of(0, 1)));
assertTrue(
result.contains(
List.of(1, 0)));
}
@Test
void shouldHandleSingleElement() {
List<List<Integer>> result =
solution.permute(
new int[]{5});
assertEquals(
List.of(List.of(5)),
result);
}
@Test
void shouldHandleEmptyArray() {
List<List<Integer>> result =
solution.permute(
new int[]{});
assertEquals(
List.of(List.of()),
result);
}
}
Approach 2 — In-Place Swapping
Core Idea
Instead of using a separate used array, place the correct element directly at the current position by swapping.
At recursion level index:
- Treat positions before
indexas fixed. - Try every element from
indexto the end. - Swap the selected element into position
index. - Recurse for the next position.
- Swap back to restore the original state.
This approach modifies the input array temporarily and restores it after each recursive call.
Swapping Intuition
For:
nums = [1,2,3]
At index 0, any element may occupy the first position.
Swap 1 into index 0
[1,2,3]
Swap 2 into index 0
[2,1,3]
Swap 3 into index 0
[3,2,1]
After fixing the first position, recurse to fix the second position.
In-Place Decision Tree
graph TD
N_1_0_0["1"] --> index_1_1["index"]
N_1_0_0["1"] --> N_0_1_2["0"]
index_1_1["index"] --> keep_2_1["keep"]
index_1_1["index"] --> N_1_2_2["1"]
N_0_1_2["0"] --> swap_2_3["swap"]
N_0_1_2["0"] --> N_1_2_4["1"]
keep_2_1["keep"] --> N_1_3_1["1"]
keep_2_1["keep"] --> N_2_3_2["2"]
N_1_2_2["1"] --> N_3_3_3["3"]
N_1_2_2["1"] --> N_2_3_4["2"]
swap_2_3["swap"] --> N_1_3_5["1"]
swap_2_3["swap"] --> N_3_3_6["3"]
N_1_2_4["1"] --> N_3_3_7["3"]
N_1_2_4["1"] --> N_2_3_8["2"]
N_2_2_4["2"] --> N_1_3_9["1"]
N_1_3_1["1"] --> index_4_1["index"]
N_1_3_1["1"] --> N_1_4_2["1"]
N_2_3_2["2"] --> index_4_3["index"]
N_2_3_2["2"] --> N_1_4_4["1"]
N_3_3_3["3"] --> index_4_5["index"]
N_3_3_3["3"] --> N_1_4_6["1"]
index_4_1["index"] --> N_1_5_1["1"]
index_4_1["index"] --> N_2_5_2["2"]
N_1_4_2["1"] --> N_3_5_3["3"]
N_1_4_2["1"] --> N_1_5_4["1"]
index_4_3["index"] --> N_3_5_5["3"]
index_4_3["index"] --> N_2_5_6["2"]
N_1_4_4["1"] --> N_2_5_7["2"]
N_1_4_4["1"] --> N_1_5_8["1"]
index_4_5["index"] --> N_3_5_9["3"]
index_4_5["index"] --> N_2_5_10["2"]
N_1_4_6["1"] --> N_3_5_11["3"]
N_1_4_6["1"] --> N_1_5_12["1"]
Every recursion level fixes one array position.
Java Code — In-Place Swapping
import java.util.ArrayList;
import java.util.List;
public class PermutationsUsingSwapping {
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 index,
List<List<Integer>> result) {
if (index == nums.length) {
List<Integer> permutation =
new ArrayList<>(
nums.length);
for (int number : nums) {
permutation.add(number);
}
result.add(permutation);
return;
}
for (int i = index;
i < nums.length;
i++) {
swap(
nums,
index,
i);
backtrack(
nums,
index + 1,
result);
swap(
nums,
index,
i);
}
}
private void swap(
int[] nums,
int first,
int second) {
int temp = nums[first];
nums[first] = nums[second];
nums[second] = temp;
}
}
Choose–Explore–Unchoose with Swapping
Choose
swap(nums, index, i);
The selected element is moved into the current fixed position.
Explore
backtrack(
nums,
index + 1,
result);
The next array position is filled.
Unchoose
swap(nums, index, i);
The original order is restored before exploring the next branch.
Why Swap Back?
The array is shared by all recursive calls.
Suppose:
nums = [1,2,3]
After generating permutations beginning with 1, the array may temporarily become:
[1,3,2]
Before generating a branch beginning with 2, the algorithm must restore the original state.
Without swapping back, sibling branches would start from a corrupted arrangement.
Detailed Swap Dry Run
Input:
[1,2,3]
Initial call:
index = 0
nums = [1,2,3]
First Branch — Keep 1 at Index 0
Swap:
swap(0,0)
Array remains:
[1,2,3]
Recurse:
index = 1
Keep 2 at Index 1
Swap:
swap(1,1)
Array:
[1,2,3]
Recurse:
index = 2
Keep 3 at Index 2
swap(2,2)
Complete permutation:
[1,2,3]
Save it.
Swap back:
swap(2,2)
Return to index 1.
Swap back:
swap(1,1)
Move 3 to Index 1
Swap:
swap(1,2)
Array becomes:
[1,3,2]
Recurse to index 2.
Complete permutation:
[1,3,2]
Save it.
Swap back:
swap(1,2)
Array restored:
[1,2,3]
Return to index 0.
Second Branch — Move 2 to Index 0
Swap:
swap(0,1)
Array:
[2,1,3]
Permutations generated:
[2,1,3]
[2,3,1]
Swap back:
swap(0,1)
Restore:
[1,2,3]
Third Branch — Move 3 to Index 0
Swap:
swap(0,2)
Array:
[3,2,1]
Permutations generated:
[3,2,1]
[3,1,2]
Swap back:
swap(0,2)
Restore:
[1,2,3]
Swap Dry Run Table
| Index | Swap | Array After Swap | Result |
|---|---|---|---|
| 0 | (0,0) |
[1,2,3] |
Continue |
| 1 | (1,1) |
[1,2,3] |
Continue |
| 2 | (2,2) |
[1,2,3] |
Save |
| 1 | (1,2) |
[1,3,2] |
Save |
| 0 | (0,1) |
[2,1,3] |
Continue |
| 1 | (1,1) |
[2,1,3] |
Save |
| 1 | (1,2) |
[2,3,1] |
Save |
| 0 | (0,2) |
[3,2,1] |
Continue |
| 1 | (1,1) |
[3,2,1] |
Save |
| 1 | (1,2) |
[3,1,2] |
Save |
Visited Array vs In-Place Swapping
| Visited Array | In-Place Swapping |
|---|---|
| Maintains a separate path | Uses input array as state |
Requires boolean[] used |
No used array |
| Easier for beginners | More space-efficient state |
| Input remains unchanged throughout traversal | Input is temporarily modified |
| Easy to adapt to object lists | Very natural for arrays |
| Duplicate pruning uses sorted input and usage rules | Duplicate pruning uses same-level value tracking |
Both approaches have the same asymptotic complexity.
Complexity of Swapping Approach
There are:
n!
complete permutations.
Each permutation must be copied from the array into a list.
Copying costs:
O(n)
Therefore:
Time = O(n × n!)
Auxiliary recursion depth:
O(n)
No used array is required.
Approach 3 — Iterative Permutation Construction
Core Idea
Start with an empty permutation.
For every input number, insert it into every possible position of every existing permutation.
Example:
nums = [1,2,3]
Start:
[[]]
Process 1:
[[1]]
Process 2:
[
[2,1],
[1,2]
]
Process 3:
[
[3,2,1],
[2,3,1],
[2,1,3],
[3,1,2],
[1,3,2],
[1,2,3]
]
Java Code — Iterative Insertion
import java.util.ArrayList;
import java.util.List;
public class PermutationsIterative {
public List<List<Integer>> permute(
int[] nums) {
List<List<Integer>> result =
new ArrayList<>();
result.add(
new ArrayList<>());
for (int number : nums) {
List<List<Integer>> next =
new ArrayList<>();
for (List<Integer> permutation
: result) {
for (int position = 0;
position <= permutation.size();
position++) {
List<Integer> candidate =
new ArrayList<>(
permutation);
candidate.add(
position,
number);
next.add(candidate);
}
}
result = next;
}
return result;
}
}
Iterative Complexity
| Complexity | Value |
|---|---|
| Time | O(n × n!) |
| Output Space | O(n × n!) |
| Recursion Stack | O(1) |
The approach avoids recursion but creates many intermediate lists.
Backtracking is usually more memory-efficient during construction.
Approach 4 — Lexicographic Permutation Generation
Core Idea
If the array is sorted, permutations can be generated in lexicographic order using the Next Permutation algorithm.
For:
[1,2,3]
the lexicographic sequence is:
[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]
Repeatedly apply nextPermutation() until no larger ordering exists.
Next Permutation Algorithm
To find the next lexicographically greater arrangement:
- Find the first decreasing position from the right.
- Find the smallest larger element to its right.
- Swap them.
- Reverse the suffix.
Java Code — Next Permutation
public class NextPermutation {
public boolean nextPermutation(
int[] nums) {
int pivot =
nums.length - 2;
while (pivot >= 0
&& nums[pivot]
>= nums[pivot + 1]) {
pivot--;
}
if (pivot < 0) {
reverse(
nums,
0,
nums.length - 1);
return false;
}
int successor =
nums.length - 1;
while (nums[successor]
<= nums[pivot]) {
successor--;
}
swap(
nums,
pivot,
successor);
reverse(
nums,
pivot + 1,
nums.length - 1);
return true;
}
private void reverse(
int[] nums,
int left,
int right) {
while (left < right) {
swap(
nums,
left++,
right--);
}
}
private void swap(
int[] nums,
int first,
int second) {
int temp = nums[first];
nums[first] = nums[second];
nums[second] = temp;
}
}
Generate All Permutations Lexicographically
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class LexicographicPermutations {
public List<List<Integer>> permute(
int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result =
new ArrayList<>();
do {
result.add(
toList(nums));
} while (nextPermutation(nums));
return result;
}
private List<Integer> toList(
int[] nums) {
List<Integer> result =
new ArrayList<>(
nums.length);
for (int number : nums) {
result.add(number);
}
return result;
}
private boolean nextPermutation(
int[] nums) {
int pivot =
nums.length - 2;
while (pivot >= 0
&& nums[pivot]
>= nums[pivot + 1]) {
pivot--;
}
if (pivot < 0) {
return false;
}
int successor =
nums.length - 1;
while (nums[successor]
<= nums[pivot]) {
successor--;
}
swap(
nums,
pivot,
successor);
reverse(
nums,
pivot + 1,
nums.length - 1);
return true;
}
private void reverse(
int[] nums,
int left,
int right) {
while (left < right) {
swap(
nums,
left++,
right--);
}
}
private void swap(
int[] nums,
int first,
int second) {
int temp = nums[first];
nums[first] = nums[second];
nums[second] = temp;
}
}
When Is Lexicographic Generation Useful?
Use it when:
- Permutations must be sorted.
- Only the next arrangement is required.
- Recursion should be avoided.
- The input is naturally orderable.
- Memory should be limited to the current arrangement.
For generating all permutations in interviews, backtracking is usually easier to explain.
Handling Duplicate Values — Permutations II
LeetCode #46 assumes all values are unique.
A common follow-up provides duplicate values.
Example:
nums = [1,1,2]
Expected unique permutations:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
Naive backtracking may generate duplicates because the two 1 values can be selected in interchangeable ways.
This becomes LeetCode #47 — Permutations II.
Duplicate Handling Strategy
Use these steps:
- Sort the array.
- Use a
usedarray. - Skip a duplicate when the previous identical value has not been used in the current branch.
Condition:
if (i > 0
&& nums[i] == nums[i - 1]
&& !used[i - 1]) {
continue;
}
Why This Duplicate Rule Works
For:
[1a,1b,2]
At the same recursion level, choose 1a before 1b.
If 1a is still available and 1b is chosen first, that branch duplicates a branch already generated by choosing 1a.
Therefore, skip 1b when:
1a has not been used
But if 1a is already in the current path, then 1b may be selected next.
This allows:
[1,1,2]
while avoiding duplicate top-level branches.
Java Code — Unique Permutations
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class UniquePermutations {
public List<List<Integer>> permuteUnique(
int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result =
new ArrayList<>();
boolean[] used =
new boolean[nums.length];
backtrack(
nums,
used,
new ArrayList<>(),
result);
return result;
}
private void backtrack(
int[] nums,
boolean[] used,
List<Integer> current,
List<List<Integer>> result) {
if (current.size()
== nums.length) {
result.add(
new ArrayList<>(
current));
return;
}
for (int i = 0;
i < nums.length;
i++) {
if (used[i]) {
continue;
}
if (i > 0
&& nums[i]
== nums[i - 1]
&& !used[i - 1]) {
continue;
}
used[i] = true;
current.add(nums[i]);
backtrack(
nums,
used,
current,
result);
current.remove(
current.size() - 1);
used[i] = false;
}
}
}
Dry Run with Duplicates
Input:
[1,1,2]
Sorted:
[1,1,2]
At the root:
- Choose the first
1. - Skip the second
1because the previous identical1is unused. - Choose
2.
This prevents generating the same set of permutations twice.
Valid results:
[1,1,2]
[1,2,1]
[2,1,1]
Unique Permutation Count
For n elements with duplicate frequencies:
n!
───────────────
f1! × f2! × ...
Example:
[1,1,2]
There are:
3!
────
2!
=
3
unique permutations.
Duplicate Handling with In-Place Swapping
When using swapping, use a Set at each recursion level to avoid placing the same value into the same position more than once.
Java Code — Unique Permutations with Swapping
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class UniquePermutationsUsingSwaps {
public List<List<Integer>> permuteUnique(
int[] nums) {
List<List<Integer>> result =
new ArrayList<>();
backtrack(
nums,
0,
result);
return result;
}
private void backtrack(
int[] nums,
int index,
List<List<Integer>> result) {
if (index == nums.length) {
List<Integer> permutation =
new ArrayList<>(
nums.length);
for (int number : nums) {
permutation.add(number);
}
result.add(permutation);
return;
}
Set<Integer> usedAtLevel =
new HashSet<>();
for (int i = index;
i < nums.length;
i++) {
if (!usedAtLevel.add(nums[i])) {
continue;
}
swap(
nums,
index,
i);
backtrack(
nums,
index + 1,
result);
swap(
nums,
index,
i);
}
}
private void swap(
int[] nums,
int first,
int second) {
int temp = nums[first];
nums[first] = nums[second];
nums[second] = temp;
}
}
Common Duplicate-Pruning Mistakes
Mistake 1 — Skipping Every Equal Value
Incorrect logic may prevent valid results such as:
[1,1,2]
Duplicates should be skipped only when they represent the same choice at the same recursion level.
Mistake 2 — Forgetting to Sort
The visited-array pruning condition depends on equal values being adjacent.
Therefore:
Arrays.sort(nums);
is required.
Mistake 3 — Using the Wrong Used Condition
Correct:
!used[i - 1]
This means the previous duplicate has not been selected in the current branch, so selecting the current duplicate would create a repeated branch.
Constrained Permutations
Backtracking becomes more useful when not every ordering is valid.
Example constraints:
- A task must appear before another task.
- Two values cannot be adjacent.
- A specific value cannot appear first.
- Some positions accept only certain values.
- The total score must remain below a threshold.
Example — No Adjacent Equal Category
Suppose tasks have categories and two tasks from the same category cannot appear next to each other.
A pruning condition can reject the choice before recursion.
private boolean canChoose(
List<Task> current,
Task candidate) {
if (current.isEmpty()) {
return true;
}
Task previous =
current.get(
current.size() - 1);
return !previous.category()
.equals(
candidate.category());
}
Pruning avoids exploring invalid branches.
Example — Dependency-Aware Ordering
Suppose task B requires task A to appear first.
Before choosing B, verify that A is already in the current path.
This turns plain permutation generation into constrained scheduling.
For larger dependency graphs, topological sorting is usually more appropriate than enumerating every ordering.
Pruning Strategy
General pruning flow:
graph TD
Try_Candidate["Try Candidate"] --> Violates_Constraint["Violates Constraint?"]
Violates_Constraint["Violates Constraint?"] --> Recurse["Recurse"]
The earlier an invalid branch is rejected, the more work is avoided.
Lazy Permutation Generation
Storing all permutations requires enormous memory.
Instead, process each permutation immediately.
Example interface:
Consumer<List<Integer>>
Java Code — Process Permutations Lazily
import java.util.ArrayList;
import java.util.List;
import java.util.function.Consumer;
public class LazyPermutationProcessor {
public void generate(
int[] nums,
Consumer<List<Integer>> consumer) {
boolean[] used =
new boolean[nums.length];
backtrack(
nums,
used,
new ArrayList<>(),
consumer);
}
private void backtrack(
int[] nums,
boolean[] used,
List<Integer> current,
Consumer<List<Integer>> consumer) {
if (current.size()
== nums.length) {
consumer.accept(
List.copyOf(current));
return;
}
for (int i = 0;
i < nums.length;
i++) {
if (used[i]) {
continue;
}
used[i] = true;
current.add(nums[i]);
backtrack(
nums,
used,
current,
consumer);
current.remove(
current.size() - 1);
used[i] = false;
}
}
}
Usage:
processor.generate(
new int[]{1, 2, 3},
System.out::println);
This reduces retained output memory, but total computation remains factorial.
Stop After Finding One Valid Permutation
Some problems require only one arrangement satisfying constraints.
Return a boolean from the recursive method.
private boolean backtrack(...) {
if (solutionComplete) {
return true;
}
for (Choice choice : choices) {
if (!valid(choice)) {
continue;
}
choose(choice);
if (backtrack(...)) {
return true;
}
unchoose(choice);
}
return false;
}
This avoids generating unnecessary solutions after a valid one is found.
K-th Permutation
A common follow-up asks for the k-th permutation without generating all previous permutations.
This becomes LeetCode #60 — Permutation Sequence.
Use factorial blocks.
For n numbers:
(n - 1)!
permutations begin with each possible first element.
Determine which block contains k, select that element, and continue with the remaining numbers.
Typical complexity:
O(n²)
using a list, or better with advanced data structures.
Example — K-th Permutation
For:
n = 3
Permutations:
1. 123
2. 132
3. 213
4. 231
5. 312
6. 321
For:
k = 4
the answer is:
231
No complete permutation tree is required.
Generate Permutations of Length k
Sometimes only k positions are required from n values.
The count is:
P(n,k)
=
n!
───────
(n-k)!
Change the base condition to:
current.size() == k
Java Code — Length-k Permutations
import java.util.ArrayList;
import java.util.List;
public class PermutationsOfLengthK {
public List<List<Integer>> permute(
int[] nums,
int k) {
if (k < 0 || k > nums.length) {
throw new IllegalArgumentException(
"Invalid permutation length");
}
List<List<Integer>> result =
new ArrayList<>();
boolean[] used =
new boolean[nums.length];
backtrack(
nums,
k,
used,
new ArrayList<>(),
result);
return result;
}
private void backtrack(
int[] nums,
int k,
boolean[] used,
List<Integer> current,
List<List<Integer>> result) {
if (current.size() == k) {
result.add(
new ArrayList<>(
current));
return;
}
for (int i = 0;
i < nums.length;
i++) {
if (used[i]) {
continue;
}
used[i] = true;
current.add(nums[i]);
backtrack(
nums,
k,
used,
current,
result);
current.remove(
current.size() - 1);
used[i] = false;
}
}
}
Parallelizing Permutations
Top-level branches are independent.
For example, permutations beginning with:
1
are independent from those beginning with:
2
This allows branch-level parallelism.
However:
- Factorial output remains enormous.
- Result merging requires coordination.
- Thread creation adds overhead.
- Shared state must be avoided.
- Recursive parallelism can overwhelm the thread pool.
Parallelization should be used only for large, CPU-intensive, pruned searches.
When Permutation Generation Becomes Infeasible
Factorial growth is extremely fast.
| n | n! |
|---|---|
| 5 | 120 |
| 8 | 40,320 |
| 10 | 3,628,800 |
| 12 | 479,001,600 |
| 15 | 1,307,674,368,000 |
For large n, consider:
- Finding only one valid arrangement
- Counting instead of generating
- Finding only the k-th arrangement
- Sampling
- Dynamic programming
- Branch and bound
- Constraint programming
- Greedy or approximation algorithms
Production Applications
Permutation logic appears in:
- Job scheduling
- Delivery route ordering
- Test execution sequences
- Workflow simulation
- Assignment problems
- Password search spaces
- Feature-priority ordering
- Deployment sequence analysis
- Game move ordering
- Manufacturing process planning
In real systems, constraints and optimization are usually added to avoid exploring all n! possibilities.
Real-World Example — Deployment Ordering
Suppose an application has three deployment steps:
Database Migration
Backend Deployment
Frontend Deployment
Potential sequences include:
Database → Backend → Frontend
Database → Frontend → Backend
Backend → Database → Frontend
...
Some sequences may be invalid.
For example:
Backend
may require the database migration first.
Backtracking can generate only valid sequences by pruning branches where dependencies are violated.
For large dependency systems, topological sorting is more efficient when every valid order does not need to be enumerated.
Real-World Example — Assignment Testing
Suppose three engineers can be assigned to three independent tasks.
Every complete assignment represents a permutation.
Engineer A → Task 1
Engineer B → Task 2
Engineer C → Task 3
Another permutation assigns them differently.
For optimization problems, evaluate each assignment's score and track the best one.
For larger assignment problems, algorithms such as the Hungarian Algorithm are more appropriate.
Backtracking vs Next Permutation
| Backtracking | Next Permutation |
|---|---|
| Explores a recursion tree | Moves to next lexicographic arrangement |
| Easy to add constraints | Best for ordered iteration |
| Can prune branches | No natural constraint pruning |
| Generates from arbitrary order | Usually starts from sorted order |
| Uses recursion or explicit stack | Iterative |
| Best for interview fundamentals | Best when only next ordering is needed |
Backtracking vs Dynamic Programming
| Backtracking | Dynamic Programming |
|---|---|
| Enumerates arrangements | Reuses overlapping states |
| Suitable for listing answers | Suitable for counts or optimum values |
| Often factorial | Can reduce repeated computation |
| Uses choose/explore/unchoose | Uses recurrence and caching |
| Easy to add direct constraints | Good when state repetition exists |
If the problem asks to list every permutation, factorial work is unavoidable.
If the problem asks for only a count or optimum, dynamic programming may avoid generating every arrangement.
Senior-Level Follow-Up Questions
How Would You Generate Permutations Without Recursion?
Options include:
- Iterative insertion
- Next Permutation
- Heap’s Algorithm
- Explicit stack simulation
What Is Heap’s Algorithm?
Heap’s Algorithm generates permutations through a carefully designed sequence of swaps.
It reduces unnecessary movement and can generate permutations in-place.
For interview clarity, standard swap-based backtracking is generally easier.
How Would You Handle Objects Instead of Integers?
The same algorithm works with:
List<T>
Use equality carefully when duplicate objects may exist.
For unique objects, identity or stable IDs may be safer than mutable business fields.
How Would You Make the Result Thread-Safe?
Avoid sharing mutable path or array state across threads.
Each parallel branch should receive:
- Its own copied state
- Its own result container
Merge results afterward.
Using a synchronized shared result list alone does not make shared recursive state safe.
Can Memoization Improve Permutation Generation?
Not when every permutation must be returned.
Each path represents a distinct output.
Memoization may help only when:
- The problem asks for a count.
- Multiple recursive states are equivalent.
- Additional constraints create overlapping subproblems.
How Would You Benchmark Permutation Implementations?
Use JMH rather than manual timing.
Compare:
- Visited-array backtracking
- Swap-based backtracking
- Iterative insertion
- Lexicographic generation
Measure:
- Execution time
- Allocation rate
- GC pressure
- Peak memory
- Input size scalability
Common Interview Questions
Interviewers frequently ask:
- Why does the loop begin at zero in the visited-array approach?
- Why does the swapping loop begin at
index? - Why must swaps be undone?
- What is the difference between permutations and subsets?
- Why are there
n!permutations? - Why is total time O(n × n!)?
- How do you handle duplicate values?
- How do you generate unique permutations?
- Can the algorithm work without extra space?
- How do you generate only length-
kpermutations? - How do you find the k-th permutation?
- Can results be generated lazily?
- Can permutation generation be parallelized?
- When does exhaustive generation become impractical?
Strong Interview Explanation
I can solve this using backtracking. Each recursion level represents one position in the permutation. I try every element that has not yet been selected, choose it, recurse to fill the next position, and then undo the choice. A visited array provides the clearest implementation. An alternative is to swap candidates directly into the current position and swap back afterward. There are
n!permutations, and copying each result costs O(n), so the total time is O(n × n!) with O(n) auxiliary recursion state.
For duplicate input:
I first sort the array. Then I skip an element when it equals the previous element and the previous identical element has not been used in the current branch. This prevents choosing equivalent duplicates at the same recursion level while still allowing both duplicates inside one permutation.
Additional Unit Tests — Swapping Solution
import static org.junit.jupiter.api.Assertions.assertArrayEquals;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;
import java.util.List;
import org.junit.jupiter.api.Test;
class PermutationsUsingSwappingTest {
private final PermutationsUsingSwapping solution =
new PermutationsUsingSwapping();
@Test
void shouldGenerateSixPermutations() {
int[] nums = {1, 2, 3};
List<List<Integer>> result =
solution.permute(nums);
assertEquals(
6,
result.size());
assertTrue(
result.contains(
List.of(1, 2, 3)));
assertTrue(
result.contains(
List.of(3, 2, 1)));
assertArrayEquals(
new int[]{1, 2, 3},
nums);
}
@Test
void shouldRestoreInputArray() {
int[] nums = {4, 5};
solution.permute(nums);
assertArrayEquals(
new int[]{4, 5},
nums);
}
@Test
void shouldHandleSingleValue() {
List<List<Integer>> result =
solution.permute(
new int[]{7});
assertEquals(
List.of(List.of(7)),
result);
}
}
Unit Tests — Unique Permutations
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import org.junit.jupiter.api.Test;
class UniquePermutationsTest {
private final UniquePermutations solution =
new UniquePermutations();
@Test
void shouldGenerateUniquePermutations() {
List<List<Integer>> result =
solution.permuteUnique(
new int[]{1, 1, 2});
assertEquals(
3,
result.size());
assertTrue(
result.contains(
List.of(1, 1, 2)));
assertTrue(
result.contains(
List.of(1, 2, 1)));
assertTrue(
result.contains(
List.of(2, 1, 1)));
}
@Test
void shouldNotContainDuplicates() {
List<List<Integer>> result =
solution.permuteUnique(
new int[]{1, 1, 2, 2});
Set<List<Integer>> unique =
new HashSet<>(result);
assertEquals(
result.size(),
unique.size());
assertEquals(
6,
result.size());
}
@Test
void shouldHandleAllEqualValues() {
List<List<Integer>> result =
solution.permuteUnique(
new int[]{2, 2, 2});
assertEquals(
List.of(
List.of(2, 2, 2)),
result);
}
}
Complete Approach Comparison
| Approach | Time | Auxiliary Space | Modifies Input Temporarily | Duplicate Support |
|---|---|---|---|---|
| Visited-array backtracking | O(n × n!) | O(n) | No | Yes, with sorting and pruning |
| Swap-based backtracking | O(n × n!) | O(n) stack | Yes | Yes, with level set |
| Iterative insertion | O(n × n!) | High intermediate allocation | No | Requires deduplication logic |
| Next Permutation | O(n × n!) for all outputs | O(1), excluding output | Yes | Naturally supports sorted unique sequence |
| Heap’s Algorithm | O(n × n!) including copies | O(n) stack | Yes | Requires duplicate handling |
Final Summary
The Permutations problem is a fundamental backtracking problem where every recursion level fills one position.
The visited-array solution is usually the clearest:
graph TD
Try_every_unused_element["Try every unused element"] --> Mark_used["Mark used"]
Mark_used["Mark used"] --> Add_to_current_path["Add to current path"]
Add_to_current_path["Add to current path"] --> Recurse["Recurse"]
Recurse["Recurse"] --> Remove["Remove"]
Remove["Remove"] --> Mark_unused["Mark unused"]
The in-place swapping solution removes the used array by moving each candidate directly into the current position.
For duplicate input:
- Sort the array.
- Track used indexes.
- Skip equal values when the previous duplicate has not been used in the current branch.
For n unique elements:
Number of permutations = n!
Complete complexity:
Time: O(n × n!)
Auxiliary Space: O(n)
Output Space: O(n × n!)
Permutation generation is inherently factorial, so real production systems usually add constraints, pruning, lazy processing, or specialized optimization algorithms.
Key Takeaways
- A permutation is an ordered arrangement.
- Order matters, unlike subsets and combinations.
nunique elements producen!permutations.- Every recursion level fills one position.
- The visited-array approach is easiest to understand.
- The swap-based approach uses the input array as recursive state.
- Always restore mutable state after recursion.
- Copy completed permutations before storing them.
- Use sorting and duplicate pruning for Permutations II.
- The duplicate rule must distinguish recursion levels from current-path usage.
- Iterative insertion is a valid non-recursive alternative.
- Next Permutation generates lexicographic order efficiently.
- Generate results lazily when storing all permutations is unnecessary.
- Use pruning when only constrained permutations are valid.
- Use factorial blocks to find the k-th permutation directly.
- Exhaustive generation becomes impractical very quickly.
- Consider topological sorting, assignment algorithms, or optimization techniques for large real-world problems.