46. Permutations

At a Glance

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

Problem (one-liner)

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

Recognition Cues

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

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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;
}