46. Permutations

Quick Identifier

Topic: backtracking
Pattern: DFS / Backtracking
Difficulty: Medium
Companies: Amazon, Meta, Google, Microsoft, Bloomberg
Frequency: Very High
LeetCode: 46

Quick Sights

Time Complexity: O(n * n!) from the optimal approach.
Space Complexity: O(recursion depth) excluding the final output unless stated.
Core Mechanism: Given distinct integers, return all n! permutations (any order in outer list).

Concept Explanation

Given distinct integers, return all n! permutations (any order in outer list).

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

Order matters — full arrangements
Distinct elements → no duplicate handling
Use visited boolean array or swap-based recursion

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Next permutation repeated — possible but indirect.
Optimal — DFS pick unused elements — O(n * n!) time for output size.

Optimal Solution

Go

func permute(nums []int) [][]int {
	result := [][]int{}
	path := make([]int, 0, len(nums))
	visited := make([]bool, len(nums))

	var dfs func()
	dfs = func() {
		if len(path) == len(nums) {
			copied := make([]int, len(path))
			copy(copied, path)
			result = append(result, copied)
			return
		}
		for index := range nums {
			if visited[index] {
				continue
			}
			visited[index] = true
			path = append(path, nums[index])
			dfs()
			path = path[:len(path)-1]
			visited[index] = false
		}
	}
	dfs()
	return result
}

JavaScript

function permute(nums) {
  const result = [];
  const path = [];
  const visited = new Array(nums.length).fill(false);

  function dfs() {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }
    for (let index = 0; index < nums.length; index += 1) {
      if (visited[index]) {
        continue;
      }
      visited[index] = true;
      path.push(nums[index]);
      dfs();
      path.pop();
      visited[index] = false;
    }
  }

  dfs();
  return result;
}