Permutations | Backtracking

leetcode.com

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