46. 全排列

力扣题目链接 (opens new window)

题目描述

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

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

思路

排列和组合最大的区别是什么？排列有顺序，[1,2] 和 [2,1] 是两个不同结果。

所以排列问题不能使用 startIndex 限制下一层的起点，每一层都要从下标 0 开始搜索。但一个排列中同一个元素不能重复选择，因此需要 used 数组记录哪些元素已经放进当前 path。

回溯三部曲：

1. 递归参数传入 nums 和 used，path 保存当前排列。
2. 当 path.size() == nums.size() 时，收集一个完整排列。
3. 每层从头遍历数组，跳过 used[i]；选择元素后标记为已用，递归返回时同时撤销路径和标记。

这里的 used 表示的是当前树枝上使用过的元素，不是某个元素在整棵搜索树中只能用一次。

模拟过程

以 nums = [1,2,3] 为例，第一层选择 1 后，used = [true,false,false]；第二层不能再选 1，只能选择 2 或 3。得到 [1,2,3] 后逐层回溯，撤销 3、2 的标记，再走出 [1,3,2]。

回到根节点后，1 的标记也被撤销，因此下一条树枝仍然可以在 [2,1,3] 中使用 1。这正是排列不使用 startIndex 的原因。

解题代码

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, vector<bool>& used) {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (used[i]) continue; // 当前排列中已经使用过
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, used);
            path.pop_back();
            used[i] = false;
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        result.clear(); path.clear();
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

复杂度分析

• 时间复杂度：O(n × n!)，共 n! 个排列，每次复制长度为 n 的路径。
• 空间复杂度：O(n)，不计返回结果，路径、used 和递归栈均为 O(n)。

其他语言

Python3

class Solution:
    def permute(self, nums):
        result, path, used = [], [], [False] * len(nums)
        def backtracking():
            if len(path) == len(nums):
                result.append(path[:]); return
            for i in range(len(nums)):
                if used[i]: continue
                used[i] = True; path.append(nums[i])
                backtracking()
                path.pop(); used[i] = False
        backtracking()
        return result

Java

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) { backtracking(nums, new boolean[nums.length]); return result; }
    void backtracking(int[] nums, boolean[] used) {
        if (path.size() == nums.length) { result.add(new ArrayList<>(path)); return; }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true; path.add(nums[i]); backtracking(nums, used);
            path.removeLast(); used[i] = false;
        }
    }
}

Go

func permute(nums []int) [][]int {
    result, path, used := [][]int{}, []int{}, make([]bool, len(nums))
    var dfs func()
    dfs = func() {
        if len(path) == len(nums) { result = append(result, append([]int{}, path...)); return }
        for i := 0; i < len(nums); i++ {
            if used[i] { continue }
            used[i] = true; path = append(path, nums[i]); dfs()
            path = path[:len(path)-1]; used[i] = false
        }
    }
    dfs(); return result
}

JS

var permute = function(nums) {
    const result = [], path = [], used = Array(nums.length).fill(false);
    function backtracking() {
        if (path.length === nums.length) { result.push([...path]); return; }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true; path.push(nums[i]); backtracking();
            path.pop(); used[i] = false;
        }
    }
    backtracking(); return result;
};

与代码随想录联系

主站46.全排列详细对比了排列和组合：组合用 startIndex 控制选择范围，排列每层从头搜索并用 used 记录当前路径。如果这个区别没想透，建议再和77.组合放在一起看。