268. Permutations
🔗 LeetCode Problem: 46. Permutations
📊 Difficulty: Medium
🏷️ Topics: Array, Backtracking
Problem Statement
Given an array nums of distinct integers, return all possible permutations. You can return the answer 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]]
Constraints:
- 1 <= nums.length <= 6
- -10 <= nums[i] <= 10
- All the integers of nums are unique.
🌟 ELI5: The Simple Idea!
Think of arranging people in a line for a photo:
You have 3 people: [1, 2, 3]
How many ways can they stand in a line?
Position 1: Who stands first?
- Person 1? Then arrange [2,3] → [1,2,3], [1,3,2]
- Person 2? Then arrange [1,3] → [2,1,3], [2,3,1]
- Person 3? Then arrange [1,2] → [3,1,2], [3,2,1]
Total: 6 ways (3! = 3 × 2 × 1 = 6)
The Building Process:
Start: []
Remaining: [1,2,3]
Step 1: Pick someone for first position
Pick 1: [1], remaining: [2,3]
Pick 2: [2], remaining: [1,3]
Pick 3: [3], remaining: [1,2]
Step 2: Pick someone for second position
From [1,remaining:[2,3]]:
Pick 2: [1,2], remaining: [3]
Pick 3: [1,3], remaining: [2]
Step 3: Only one person left, add them
[1,2,3] ✓
[1,3,2] ✓
Continue for all choices...
Key Difference from Combinations:
Combinations: [1,2,3] same as [3,2,1]
Order doesn't matter
Used start index to avoid duplicates
Permutations: [1,2,3] different from [3,2,1]
Order matters!
Need to track which elements used
🎨 Visual Understanding
Decision Tree for nums=[1,2,3]
[]
/ | \
1 2 3
/ | \
[1] [2] [3]
/ \ / \ / \
2 3 1 3 1 2
/ \ / \ / \
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
| | | | | |
3 2 3 1 2 1
| | | | | |
[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]
✓ ✓ ✓ ✓ ✓ ✓
All 6 permutations found!
How Tracking Works
Using a "used" array to track which elements are already picked:
Initial: used = [false, false, false]
nums = [1, 2, 3]
Pick 1 (index 0):
used = [true, false, false]
current = [1]
Pick 2 (index 1):
used = [true, true, false]
current = [1, 2]
Pick 3 (index 2):
used = [true, true, true]
current = [1, 2, 3] ✓ Complete!
Backtrack: used = [true, true, false]
current = [1, 2]
Backtrack: used = [true, false, false]
current = [1]
Pick 3 (index 2):
used = [true, false, true]
current = [1, 3]
Pick 2 (index 1):
used = [true, true, true]
current = [1, 3, 2] ✓ Complete!
And so on...
🎯 Approach 1: Backtracking with Used Array ⭐⭐
The Most Common Solution
Algorithm:
Use backtracking with:
- Current permutation being built
- Boolean array to track used elements
Rules:
1. If current size == nums.length → Complete permutation!
2. Try each element that hasn't been used yet
3. Mark as used, recurse, then unmark (backtrack)
Implementation
import java.util.*;
/**
* Backtracking with used array
* Time: O(n! × n) - n! permutations, each takes O(n) to build
* Space: O(n) - Recursion depth + used array
*/
class Solution {
private List<List<Integer>> result;
public List<List<Integer>> permute(int[] nums) {
result = new ArrayList<>();
backtrack(nums, new ArrayList<>(), new boolean[nums.length]);
return result;
}
private void backtrack(int[] nums, List<Integer> current, boolean[] used) {
// Base case: completed permutation
if (current.size() == nums.length) {
result.add(new ArrayList<>(current));
return;
}
// Try each element
for (int i = 0; i < nums.length; i++) {
// Skip if already used
if (used[i]) {
continue;
}
// Choose
current.add(nums[i]);
used[i] = true;
// Explore
backtrack(nums, current, used);
// Unchoose (backtrack)
current.remove(current.size() - 1);
used[i] = false;
}
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.permute(new int[]{1,2,3}));
System.out.println(sol.permute(new int[]{0,1}));
}
}
⏰ Time: O(n! × n) - n! permutations, each costs O(n) to build
💾 Space: O(n) - Recursion depth + used array
🔍 Super Detailed Dry Run
Example: nums = [1, 2, 3]
Goal: Generate all 6 permutations
═══════════════════════════════════════════════════════════════
Backtrack Call Tree
═══════════════════════════════════════════════════════════════
Call 1: backtrack([1,2,3], current=[], used=[F,F,F])
size=0 < 3 (continue)
Loop i=0 (nums[0]=1):
used[0]=false → Not used ✓
current = [1]
used = [T,F,F]
→ backtrack([1,2,3], [1], [T,F,F])
═══════════════════════════════════════════════════════════════
Call 2: backtrack([1,2,3], current=[1], used=[T,F,F])
size=1 < 3 (continue)
Loop i=0:
used[0]=true → Skip (already used)
Loop i=1 (nums[1]=2):
used[1]=false → Not used ✓
current = [1, 2]
used = [T,T,F]
→ backtrack([1,2,3], [1,2], [T,T,F])
═══════════════════════════════════════════════════════════════
Call 3: backtrack([1,2,3], current=[1,2], used=[T,T,F])
size=2 < 3 (continue)
Loop i=0:
used[0]=true → Skip
Loop i=1:
used[1]=true → Skip
Loop i=2 (nums[2]=3):
used[2]=false → Not used ✓
current = [1, 2, 3]
used = [T,T,T]
→ backtrack([1,2,3], [1,2,3], [T,T,T])
═══════════════════════════════════════════════════════════════
Call 4: backtrack([1,2,3], current=[1,2,3], used=[T,T,T])
size=3 == 3 → Complete permutation!
Add [1,2,3] to result ✓
Return
Result: [[1,2,3]]
[Back to Call 3]
Backtrack:
current.remove(3) → current = [1,2]
used[2] = false → used = [T,T,F]
Loop i=2 finished
Return
[Back to Call 2]
Backtrack:
current.remove(2) → current = [1]
used[1] = false → used = [T,F,F]
Loop i=2 (nums[2]=3):
used[2]=false → Not used ✓
current = [1, 3]
used = [T,F,T]
→ backtrack([1,2,3], [1,3], [T,F,T])
═══════════════════════════════════════════════════════════════
Call 5: backtrack([1,2,3], current=[1,3], used=[T,F,T])
size=2 < 3 (continue)
Loop i=0:
used[0]=true → Skip
Loop i=1 (nums[1]=2):
used[1]=false → Not used ✓
current = [1, 3, 2]
used = [T,T,T]
→ backtrack([1,2,3], [1,3,2], [T,T,T])
═══════════════════════════════════════════════════════════════
Call 6: backtrack([1,2,3], current=[1,3,2], used=[T,T,T])
size=3 == 3 → Complete permutation!
Add [1,3,2] to result ✓
Return
Result: [[1,2,3], [1,3,2]]
[Back to Call 5, 2, 1]
Continue backtracking...
═══════════════════════════════════════════════════════════════
[Back to Call 1]
Backtrack from i=0 complete
Loop i=1 (nums[1]=2):
used[1]=false → Not used ✓
current = [2]
used = [F,T,F]
→ backtrack([1,2,3], [2], [F,T,F])
... (Similar process for starting with 2, then 3)
═══════════════════════════════════════════════════════════════
Final Result:
[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
Total: 6 permutations (3! = 6) ✓
Visual State Transitions:
Start: current=[], used=[F,F,F]
Choose 1:
current=[1], used=[T,F,F]
Choose 2:
current=[1,2], used=[T,T,F]
Choose 3:
current=[1,2,3], used=[T,T,T] → Add! ✓
Backtrack:
current=[1,2], used=[T,T,F]
Backtrack:
current=[1], used=[T,F,F]
Choose 3:
current=[1,3], used=[T,F,T]
Choose 2:
current=[1,3,2], used=[T,T,T] → Add! ✓
Pattern repeats for all starting choices!
🎯 Approach 2: Backtracking with Swap ⭐
Space-Optimized Solution
Key Idea: Instead of tracking used elements, swap elements to build permutations in-place.
import java.util.*;
/**
* Backtracking with swap
* Time: O(n! × n)
* Space: O(n) - Only recursion stack (no used array!)
*/
class Solution {
private List<List<Integer>> result;
public List<List<Integer>> permute(int[] nums) {
result = new ArrayList<>();
backtrack(nums, 0);
return result;
}
private void backtrack(int[] nums, int start) {
// Base case: reached end
if (start == nums.length) {
// Convert array to list and add
List<Integer> permutation = new ArrayList<>();
for (int num : nums) {
permutation.add(num);
}
result.add(permutation);
return;
}
// Try swapping start with each position from start to end
for (int i = start; i < nums.length; i++) {
// Swap
swap(nums, start, i);
// Recurse for next position
backtrack(nums, start + 1);
// Swap back (backtrack)
swap(nums, start, i);
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
Pros: No extra space for used array
Cons: Modifies input array (less intuitive)
How Swap Approach Works
nums = [1, 2, 3]
Position 0: Who should be at index 0?
Swap with 0: [1,2,3] → Fix 1 at pos 0
Swap with 1: [2,1,3] → Fix 2 at pos 0
Swap with 2: [3,2,1] → Fix 3 at pos 0
For [1,2,3] with 1 fixed at pos 0:
Position 1: Who should be at index 1?
Swap with 1: [1,2,3] → Fix 2 at pos 1 → [1,2,3] ✓
Swap with 2: [1,3,2] → Fix 3 at pos 1 → [1,3,2] ✓
And so on...
🎯 Approach 3: Iterative (Using Queue/BFS) ⭐
Alternative Solution
import java.util.*;
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Queue<List<Integer>> queue = new LinkedList<>();
// Start with empty permutation
queue.offer(new ArrayList<>());
// For each number in nums
for (int num : nums) {
int size = queue.size();
// Process all partial permutations at this level
for (int i = 0; i < size; i++) {
List<Integer> current = queue.poll();
// Insert num at every possible position
for (int j = 0; j <= current.size(); j++) {
List<Integer> newPerm = new ArrayList<>(current);
newPerm.add(j, num);
queue.offer(newPerm);
}
}
}
result.addAll(queue);
return result;
}
}
How it works:
nums = [1, 2, 3]
Start: [[]]
Add 1: [[1]]
Insert 1 at all positions in []
Add 2: [[2,1], [1,2]]
Insert 2 at all positions in [1]
- Position 0: [2,1]
- Position 1: [1,2]
Add 3: [[3,2,1], [2,3,1], [2,1,3], [3,1,2], [1,3,2], [1,2,3]]
Insert 3 at all positions in [2,1]
- Position 0: [3,2,1]
- Position 1: [2,3,1]
- Position 2: [2,1,3]
Insert 3 at all positions in [1,2]
- Position 0: [3,1,2]
- Position 1: [1,3,2]
- Position 2: [1,2,3]
Result: All 6 permutations!
⚠️ Common Mistakes
Mistake 1: Not creating new list when adding to result
// ❌ WRONG - All results point to same list!
if (current.size() == nums.length) {
result.add(current); // Reference!
return;
}
// ✓ CORRECT - Add a copy
if (current.size() == nums.length) {
result.add(new ArrayList<>(current));
return;
}
Mistake 2: Not backtracking used array
// ❌ WRONG - used[i] stays true!
current.add(nums[i]);
used[i] = true;
backtrack(nums, current, used);
current.remove(current.size() - 1);
// used[i] not reset!
// ✓ CORRECT - Reset everything
current.add(nums[i]);
used[i] = true;
backtrack(nums, current, used);
current.remove(current.size() - 1);
used[i] = false; // Backtrack!
Mistake 3: Using start index like in combinations
// ❌ WRONG - This is for combinations, not permutations!
for (int i = start; i < nums.length; i++) {
// Can only use elements after start
}
// Would miss [3,1,2] if we pick 3 first!
// ✓ CORRECT - Check all elements
for (int i = 0; i < nums.length; i++) {
if (!used[i]) { // Skip only if used
// Try this element
}
}
Mistake 4: Not swapping back in swap approach
// ❌ WRONG - Array gets corrupted!
swap(nums, start, i);
backtrack(nums, start + 1);
// nums array modified permanently!
// ✓ CORRECT - Swap back
swap(nums, start, i);
backtrack(nums, start + 1);
swap(nums, start, i); // Restore!
Mistake 5: Wrong base case
// ❌ WRONG - Infinite recursion!
if (current.isEmpty()) {
result.add(new ArrayList<>(current));
return;
}
// ✓ CORRECT - Check size
if (current.size() == nums.length) {
result.add(new ArrayList<>(current));
return;
}
🎯 Pattern Recognition
Problem Type: Generate All Permutations
Core Pattern: Backtracking + Used Tracking OR Swapping
When to Apply:
✓ Generate all permutations/arrangements
✓ Order matters (unlike combinations)
✓ Each element used exactly once
✓ No duplicates in input
Recognition Keywords:
- "all possible permutations"
- "all arrangements"
- "order matters"
- "distinct integers"
Combinations vs Permutations:
┌─────────────────┬──────────────┬──────────────┐
│ Feature │ Combination │ Permutation │
├─────────────────┼──────────────┼──────────────┤
│ Order matters │ No │ Yes │
│ [1,2] vs [2,1] │ Same │ Different │
│ Count (n=3) │ C(3,2)=3 │ P(3,3)=6 │
│ Start index │ Yes │ No │
│ Used tracking │ No │ Yes │
│ Formula │ n!/(k!(n-k)!)│ n! │
└─────────────────┴──────────────┴──────────────┘
Similar Problems:
- Permutations II (LC 47) - With duplicate values
- Next Permutation (LC 31) - Find next permutation
- Permutation Sequence (LC 60) - Find kth permutation
Key Components:
┌────────────────────────────────────────────┐
│ Backtracking: Try all arrangements │
│ Used array: Track picked elements │
│ Base case: current.size() == nums.length │
│ No start index: Try all positions │
│ Alternative: Swap approach (in-place) │
│ Time: O(n! × n), Space: O(n) │
└────────────────────────────────────────────┘
🧠 Interview Strategy
Step 1: "This is a permutation problem - order matters"
Step 2: "I'll use backtracking with a used array"
Step 3: "Try each unused element at each position"
Key Points to Mention:
- Permutation vs Combination: order matters here
- Need to track which elements are used
- No start index (unlike combinations)
- Base case: when size equals nums.length
- Total permutations: n!
Walk Through Example:
"For nums=[1,2,3]:
Start with empty []
Try 1 first:
[1] → Try 2: [1,2] → Add 3: [1,2,3] ✓
[1] → Try 3: [1,3] → Add 2: [1,3,2] ✓
Try 2 first:
[2] → Try 1: [2,1] → Add 3: [2,1,3] ✓
[2] → Try 3: [2,3] → Add 1: [2,3,1] ✓
Try 3 first:
[3] → Try 1: [3,1] → Add 2: [3,1,2] ✓
[3] → Try 2: [3,2] → Add 1: [3,2,1] ✓
Total: 6 permutations (3! = 6)"
Why Used Array:
"Unlike combinations where we use start index,
permutations need all elements in any order.
[1,2,3] and [3,2,1] are different permutations!
So we can't restrict to elements after a start.
Instead, we track which specific elements used."
Complexity:
"Time: O(n! × n)
- Generate n! permutations
- Each takes O(n) to build and copy
Space: O(n)
- Recursion depth: n
- Used array: n
- Current list: n
Can't do better - need to generate all n! results"
Alternative Approaches:
"Can also use swap approach:
- Swap elements to build permutations
- More space efficient (no used array)
- But modifies input array
- Same time complexity"
Edge Cases:
✓ Single element: [1] → [[1]]
✓ Two elements: [1,2] → [[1,2],[2,1]]
✓ Empty array: [] → [[]]
📝 Quick Revision Notes
🎯 Core Concept:
Permutations: Generate all arrangements where order matters. Use backtracking with used array to track picked elements. Try all positions (no start index). Base case: current.size() == n. Total: n! permutations.
⚡ Quick Implementation:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Solution {
public List<List<Integer>> permute(int[] a) {
// return recursive(a);
return iterative(a);
}
private List<List<Integer>> iterative(int[] a) {
List<List<Integer>> res = new ArrayList<>();
// Concept
// Example: a=[1,2,3]
// Consider empty list in queue {}
// Take 1:
// Add at every place of the list that is coming from queue.
// In this case, since list is empty, 1 gets simply added and pushed to queue
// Take 2:
// Take next item from queue which is {1}
// Add 2 at every place in the list coming from queue
// So, it becomes {2,1} and {1,2} which gets pushed to queue.
// Take 3:
// Queue size is now 2
// For {2,1}, it gets added as {3,2,1},{2,3,1},{2,1,3}
// For {1,2}, it gets added as {3,1,2},{1,3,2},{1,2,3}
// All above gets pushed to queue and that is the result (non-popped items)
Queue<List<Integer>> queue = new LinkedList<>();
queue.offer(new ArrayList<>());
for (int i = 0; i < a.length; i++) {
int size = queue.size();
// Take 3 (queue size)
for (int j = 0; j < size; j++) {
List<Integer> polled = queue.poll();
// Take 1 step in above doc
if (polled.size() == 0) {
queue.offer(List.of(a[i]));
break;
}
int polledListSize = polled.size();
for (int k = 0; k <= polledListSize; k++) {
List<Integer> newList = new ArrayList<>(polled);
newList.add(k, a[i]);
queue.offer(newList);
}
}
}
res.addAll(queue);
return res;
}
private List<List<Integer>> recursive(int[] a) {
List<List<Integer>> res = new ArrayList<>();
recursiveUtil(a, new ArrayList<>(), new boolean[a.length], res);
return res;
}
private void recursiveUtil(int[] a, ArrayList<Integer> currList,
boolean[] visited, List<List<Integer>> res) {
// step 2: base case
if (currList.size() == a.length) {
res.add(new ArrayList<>(currList));
return;
}
// step 1: try every element except the elements in visited array.
// It means, when we take 1 in [1,2,3], we again start from i=0 and
// track that 1 is already included using visited array. Once the above
// flow completes, we remove from visited array and currList as well.
// When we take 2 in [1,2,3], we start from i=0 and track that 2 is
// already included and other elements will be considered.
for (int i = 0; i < a.length; i++) {
if (visited[i]) {
continue;
}
visited[i] = true;
currList.add(a[i]);
// before calling next, add it to currList and visited
// once call is done, remove it from currList and visited
recursiveUtil(a, currList, visited, res);
currList.remove(currList.size() - 1);
visited[i] = false;
}
}
public static void main(String[] args) {
Solution s = new Solution();
// [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
System.out.println(s.permute(new int[] { 1, 2, 3 }));
// [[0,1],[1,0]]
System.out.println(s.permute(new int[] { 0, 1 }));
}
}
🔑 Key Insights:
- Pattern: Backtracking + Used Tracking
- Order Matters: [1,2,3] ≠ [3,2,1]
- Used Array: Track which elements picked
- All Positions: No start index (try all)
- Base Case: size == nums.length
- Count: n! permutations
- Time: O(n! × n), Space: O(n) ✓
🎪 Memory Aid:
"Try all spots, mark as used, backtrack when done!"
"Permutations = arrangements, order matters!" ✨
⚠️ Critical Differences:
COMBINATIONS:
[1,2,3] same as [3,2,1]
Use start index
Count: C(n,k) = n!/(k!(n-k)!)
for (int i = start; i < n; i++) {
// Pick from start onwards
}
PERMUTATIONS:
[1,2,3] different from [3,2,1]
Use used array
Count: n!
for (int i = 0; i < n; i++) {
if (!used[i]) {
// Try any unused element
}
}
Key: Permutations care about ORDER!
🎯 Two Approaches:
Approach 1: Used Array
Pros: Clear logic, easy to understand
Cons: Extra O(n) space for used array
boolean[] used = new boolean[n];
if (!used[i]) { ... }
Approach 2: Swap
Pros: No used array, space efficient
Cons: Modifies input, less intuitive
swap(nums, i, j);
backtrack(start + 1);
swap(nums, i, j); // Restore
Both: O(n! × n) time, O(n) space
🧪 Edge Cases
Case 1: Single element
Input: nums = [1]
Output: [[1]]
Only one arrangement
Case 2: Two elements
Input: nums = [1,2]
Output: [[1,2],[2,1]]
2! = 2 permutations
Case 3: Three elements
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
3! = 6 permutations
Case 4: Negative numbers
Input: nums = [-1,0,1]
Output: All 6 permutations
Works with any distinct integers
All handled correctly! ✓
🎓 Complexity Analysis
Time Complexity: O(n! × n)
Where n = length of nums
Why?
Number of permutations: n!
- First position: n choices
- Second position: n-1 choices
- Third position: n-2 choices
- ...
- Total: n × (n-1) × (n-2) × ... × 1 = n!
Each permutation: O(n) to build
- Add n elements: O(n)
- Copy to result: O(n)
Total: n! × n
Example:
n=3: 3! × 3 = 6 × 3 = 18 operations
n=4: 4! × 4 = 24 × 4 = 96 operations
n=5: 5! × 5 = 120 × 5 = 600 operations
Grows extremely fast!
Space Complexity: O(n)
Recursion stack:
Maximum depth = n
(Building permutation position by position)
Used array: O(n)
Current list: O(n)
Total: O(n) auxiliary space
Note: Output space not counted
(Would be O(n! × n) for all results)
📚 Related Problems
Same Core Pattern: - Permutations II (LC 47) - With duplicate values (harder!) - Letter Case Permutation (LC 784) - String permutations - Palindrome Permutation II (LC 267) - Palindrome permutations
Similar Backtracking: - Combinations (LC 77) - Order doesn't matter - Subsets (LC 78) - All subsets - Combination Sum (LC 39) - Sum to target
Permutation Variations: - Next Permutation (LC 31) - Find next in order - Permutation Sequence (LC 60) - Find kth permutation - Permutation in String (LC 567) - Check if substring
Happy practicing! 🎯
Note: This is the classic permutation problem! Master this and you understand: (1) difference between permutations and combinations, (2) when order matters, (3) tracking used elements, (4) factorial time complexity. The pattern extends to many arrangement problems! Very common at FAANG - appears in system design too (arrangement of tasks, schedules, etc.)! 💪✨