LeetCode 46. 全排列

Categories:

Tags:

题目描述
思路分析
1. 解法一：回溯（used 标记）（推荐）
2. 解法二：回溯（原地交换）
相似题目

题目描述

✅ 46. 全排列

题目：

给定一个不含重复数字的整数数组 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]]

示例 3：

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

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数互不相同

思路分析

解法一：回溯（used 标记）（推荐）

核心思路：

维护一个 used 数组表示数字是否已使用。

每次从未使用的数字中选择一个加入路径，递归构造。

当路径长度等于数组长度时收集结果。

复杂度分析：

时间复杂度：O(n * n!)，其中 n 表示数组长度。

空间复杂度：O(n)，其中 n 表示递归栈深度与 used 数组大小。

// 回溯 + used 标记
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backtrack(nums, used, new ArrayList<>(), res);
        return res;
    }

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

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

// 回溯 + used 标记
func permute(nums []int) [][]int {
	var res [][]int
	used := make([]bool, len(nums))
	path := make([]int, 0, len(nums))

	var backtrack func()
	backtrack = func() {
		if len(path) == len(nums) {
			copyPath := append([]int{}, path...)
			res = append(res, copyPath)
			return
		}
		for i := 0; i < len(nums); i++ {
			if used[i] {
				continue
			}
			used[i] = true
			path = append(path, nums[i])
			backtrack()
			path = path[:len(path)-1]
			used[i] = false
		}
	}

	backtrack()
	return res
}

解法二：回溯（原地交换）

核心思路：

从位置 first 开始，依次将 nums[first] 与后面元素交换。

交换后递归处理 first + 1，回溯时再交换回来。

不需要 used 数组，节省空间。

复杂度分析：

时间复杂度：O(n * n!)，其中 n 表示数组长度。

空间复杂度：O(n)，其中 n 表示递归栈深度。

// 回溯 + 原地交换
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, 0, res);
        return res;
    }

    private void backtrack(int[] nums, int first, List<List<Integer>> res) {
        if (first == nums.length) {
            List<Integer> path = new ArrayList<>();
            for (int num : nums) {
                path.add(num);
            }
            res.add(path);
            return;
        }

        for (int i = first; i < nums.length; i++) {
            swap(nums, first, i);
            backtrack(nums, first + 1, res);
            swap(nums, first, i);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

// 回溯 + 原地交换
func permute(nums []int) [][]int {
	var res [][]int

	var backtrack func(int)
	backtrack = func(first int) {
		if first == len(nums) {
			copyPath := append([]int{}, nums...)
			res = append(res, copyPath)
			return
		}
		for i := first; i < len(nums); i++ {
			nums[first], nums[i] = nums[i], nums[first]
			backtrack(first + 1)
			nums[first], nums[i] = nums[i], nums[first]
		}
	}

	backtrack(0)
	return res
}

相似题目

题目	难度	考察点
31. 下一个排列	中等	排列规律
47. 全排列 II	中等	回溯、去重
60. 排列序列	困难	数学、回溯
77. 组合	中等	回溯
39. 组合总和	中等	回溯
78. 子集	中等	回溯
90. 子集 II	中等	回溯、去重

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/83334596