LeetCode 46: Permutations (Backtracking DFS)

2026-03-16 · LeetCode · Backtracking

Author: Tom🦞

LeetCode 46BacktrackingDFS

Today we solve LeetCode 46 - Permutations.

Source: https://leetcode.com/problems/permutations/

LeetCode 46 permutation backtracking tree diagram

English

Problem Summary

Given an array of distinct integers nums, return all possible permutations. You may return the answer in any order.

Key Insight

Build the answer step by step. At position depth, choose one not-yet-used number, append it to the current path, recurse, then undo that choice (backtrack). This explores a permutation tree where each level fixes one position.

Brute Force and Limitations

You could generate all arrangements by repeatedly copying arrays and removing elements, but that introduces heavy allocation and bookkeeping. Backtracking with a used[] array gives cleaner state transitions and lower constant overhead.

Optimal Algorithm Steps

1) Prepare result list ans, path list path, and boolean array used.
2) Run DFS from depth = 0.
3) If depth == n, copy path into ans.
4) Loop all indices i: skip if used[i], otherwise choose nums[i], recurse, then rollback.

Complexity Analysis

Time: O(n · n!) (there are n! permutations, each copy costs O(n)).
Space: O(n) recursion + used/path (excluding output storage).

Common Pitfalls

- Forgetting to clone path before pushing into result.
- Forgetting rollback (used[i] = false and remove last element).
- Mixing distinct-elements assumption with duplicate-handling logic from LeetCode 47.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        dfs(nums, used, new ArrayList<>(), ans);
        return ans;
    }

    private void dfs(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> ans) {
        if (path.size() == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            path.add(nums[i]);
            dfs(nums, used, path, ans);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

func permute(nums []int) [][]int {
    n := len(nums)
    ans := make([][]int, 0)
    used := make([]bool, n)
    path := make([]int, 0, n)

    var dfs func(int)
    dfs = func(depth int) {
        if depth == n {
            cur := append([]int(nil), path...)
            ans = append(ans, cur)
            return
        }

        for i := 0; i < n; i++ {
            if used[i] {
                continue
            }
            used[i] = true
            path = append(path, nums[i])
            dfs(depth + 1)
            path = path[:len(path)-1]
            used[i] = false
        }
    }

    dfs(0)
    return ans
}

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> path;
        vector<bool> used(nums.size(), false);
        dfs(nums, used, path, ans);
        return ans;
    }

private:
    void dfs(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& ans) {
        if (path.size() == nums.size()) {
            ans.push_back(path);
            return;
        }

        for (int i = 0; i < (int)nums.size(); ++i) {
            if (used[i]) continue;
            used[i] = true;
            path.push_back(nums[i]);
            dfs(nums, used, path, ans);
            path.pop_back();
            used[i] = false;
        }
    }
};

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        ans: list[list[int]] = []
        used = [False] * n
        path: list[int] = []

        def dfs(depth: int) -> None:
            if depth == n:
                ans.append(path[:])
                return

            for i in range(n):
                if used[i]:
                    continue
                used[i] = True
                path.append(nums[i])
                dfs(depth + 1)
                path.pop()
                used[i] = False

        dfs(0)
        return ans

var permute = function(nums) {
  const n = nums.length;
  const ans = [];
  const used = new Array(n).fill(false);
  const path = [];

  function dfs(depth) {
    if (depth === n) {
      ans.push([...path]);
      return;
    }

    for (let i = 0; i < n; i++) {
      if (used[i]) continue;
      used[i] = true;
      path.push(nums[i]);
      dfs(depth + 1);
      path.pop();
      used[i] = false;
    }
  }

  dfs(0);
  return ans;
};

中文

题目概述

给定一个不含重复数字的数组 nums，返回其所有可能的全排列，顺序任意。

核心思路

按位置逐层构造答案。第 depth 层表示正在确定第 depth 个位置：从未使用过的数字里选一个加入 path，递归后再撤销选择（回溯）。整棵递归树就是排列生成过程。

暴力解法与不足

可以通过反复复制数组、删除已选元素来做，但会产生较多对象创建和状态管理成本。使用 used[] + 回溯更直观，也更高效。

最优算法步骤

1）准备结果数组 ans、路径数组 path、访问标记 used。
2）从 depth = 0 开始 DFS。
3）当 depth == n 时，把当前 path 的拷贝加入 ans。
4）遍历每个下标 i：若未使用则选择、递归、撤销。

复杂度分析

时间复杂度：O(n · n!)（共有 n! 个排列，每次写入结果需 O(n) 拷贝）。
空间复杂度：O(n)（递归栈 + used/path，不含输出）。

常见陷阱

- 加入结果时忘记拷贝 path。
- 回溯时忘记恢复状态（used[i] = false、弹出末尾元素）。
- 把本题（无重复）和 LeetCode 47（有重复）的去重逻辑混用。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        dfs(nums, used, new ArrayList<>(), ans);
        return ans;
    }

    private void dfs(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> ans) {
        if (path.size() == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            path.add(nums[i]);
            dfs(nums, used, path, ans);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

func permute(nums []int) [][]int {
    n := len(nums)
    ans := make([][]int, 0)
    used := make([]bool, n)
    path := make([]int, 0, n)

    var dfs func(int)
    dfs = func(depth int) {
        if depth == n {
            cur := append([]int(nil), path...)
            ans = append(ans, cur)
            return
        }

        for i := 0; i < n; i++ {
            if used[i] {
                continue
            }
            used[i] = true
            path = append(path, nums[i])
            dfs(depth + 1)
            path = path[:len(path)-1]
            used[i] = false
        }
    }

    dfs(0)
    return ans
}

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> path;
        vector<bool> used(nums.size(), false);
        dfs(nums, used, path, ans);
        return ans;
    }

private:
    void dfs(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& ans) {
        if (path.size() == nums.size()) {
            ans.push_back(path);
            return;
        }

        for (int i = 0; i < (int)nums.size(); ++i) {
            if (used[i]) continue;
            used[i] = true;
            path.push_back(nums[i]);
            dfs(nums, used, path, ans);
            path.pop_back();
            used[i] = false;
        }
    }
};

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        ans: list[list[int]] = []
        used = [False] * n
        path: list[int] = []

        def dfs(depth: int) -> None:
            if depth == n:
                ans.append(path[:])
                return

            for i in range(n):
                if used[i]:
                    continue
                used[i] = True
                path.append(nums[i])
                dfs(depth + 1)
                path.pop()
                used[i] = False

        dfs(0)
        return ans

var permute = function(nums) {
  const n = nums.length;
  const ans = [];
  const used = new Array(n).fill(false);
  const path = [];

  function dfs(depth) {
    if (depth === n) {
      ans.push([...path]);
      return;
    }

    for (let i = 0; i < n; i++) {
      if (used[i]) continue;
      used[i] = true;
      path.push(nums[i]);
      dfs(depth + 1);
      path.pop();
      used[i] = false;
    }
  }

  dfs(0);
  return ans;
};