Problem Statement
Given an array nums containing distinct integers, return all possible permutations.
A permutation is an arrangement of all elements in a different order.
Brute Force Intuition
For every position, try placing each available number.
Once a number is used, it cannot be used again in the same permutation.
We keep building the permutation until all positions are filled.
Since every possible arrangement must be generated, recursion naturally fits.
Complexity
- Time Complexity: O(N! × N)
- Space Complexity: O(N)
Moving Towards the Optimal Approach
At every level:
Choose one unused number
Add it to the current permutation.
Mark it as visited.
Recurse for the next position.
After returning:
Undo the choice
This is classic Backtracking.
Pattern Recognition
Whenever you see:
- Generate all arrangements
- Ordering matters
- Every element used exactly once
Think:
Backtracking + Visited Array
Key Observation
For:
nums = [1,2,3]
At Position 1:
Choose 1
Choose 2
Choose 3
Each choice creates an entirely new branch.
Recursion Tree
[]
├── [1]
│ ├── [1,2]
│ │ └── [1,2,3]
│ │
│ └── [1,3]
│ └── [1,3,2]
│
├── [2]
│ ├── [2,1]
│ │ └── [2,1,3]
│ │
│ └── [2,3]
│ └── [2,3,1]
│
└── [3]
├── [3,1]
│ └── [3,1,2]
│
└── [3,2]
└── [3,2,1]
Optimal Java Solution
import java.util.*;
class Solution {
public List<List<Integer>> permute(int[] nums) {
boolean[] visited = new boolean[nums.length];
List<List<Integer>> ans = new ArrayList<>();
solvePermute(nums,
visited,
ans,
new ArrayList<>());
return ans;
}
private void solvePermute(int[] nums,
boolean[] visited,
List<List<Integer>> ans,
List<Integer> temp) {
if (temp.size() == nums.length) {
ans.add(new ArrayList<>(temp));
return;
}
for (int i = 0; i < nums.length; i++) {
if (visited[i])
continue;
visited[i] = true;
temp.add(nums[i]);
solvePermute(nums,
visited,
ans,
temp);
temp.remove(temp.size() - 1);
visited[i] = false;
}
}
}
Dry Run
Input
nums = [1,2,3]
Step 1
Choose:
1
Current:
[1]
Step 2
Choose:
2
Current:
[1,2]
Step 3
Choose:
3
Current:
[1,2,3]
Valid permutation
Backtrack and try other choices.
Output
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
Why Backtracking Works?
At every position:
Try every unused number
Once a choice is made:
Mark Used
Explore
Unmark Used
This guarantees every permutation is generated exactly once.
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(N! × N) |
| Space Complexity | O(N) |
Reason:
N! permutations exist
and copying each permutation takes O(N).
Interview One-Liner
Build permutations by choosing one unused element at a time, marking it visited, recursively generating the remaining positions, and backtracking afterward.
Pattern Learned
Generate All Arrangements
+
Use Every Element Once
=> Backtracking
=> Visited Array
Similar Problems
- Permutations
- Permutations II
- N Queens
- Sudoku Solver
- Word Search
- Rat in a Maze
Memory Trick
Subsets
→ Pick / Not Pick
Combination Sum
→ Pick / Not Pick + Reuse
Palindrome Partitioning
→ Try Every Cut
Permutations
→ Try Every Unused Element
Mental Model
Current Position
Choose Any Unused Number
↓
Mark Used
↓
Recurse
↓
Backtrack
Whenever you hear:
"Generate all permutations"
your brain should immediately think:
Backtracking + Visited Array + Choose Any Unused Element
![[System Design] Part 4 — Amazon CONDOR & Anticipatory Shipping](https://media2.dev.to/dynamic/image/width=1000,height=420,fit=cover,gravity=auto,format=auto/https%3A%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Farticles%2Fcr7y22086qgqejku95th.png)
