46. 全排列

🟠   🔖  数组 回溯  🔗 力扣 LeetCode

题目

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

Example 1:

Input: nums = [1,2,3]

Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]

Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]

Output: [[1]]

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

题目大意

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

解题思路

这是一个经典的回溯问题，可以通过深度优先搜索（DFS）来解决。

1. 使用一个数组 used 来标记数字是否已经被使用过，确保每个数字在排列中只使用一次，初始时都为 false。
2. 定义一个 backtrack 函数，用于搜索所有可能的排列。在函数中进行如下操作：
   • 如果当前排列的长度等于输入序列的长度，说明已经得到一个完整的排列，将其添加到结果数组中。
   • 否则，遍历输入序列的每个数字，如果当前数字没有被使用过，就将其加入当前排列中，并标记为已使用。
   • 然后递归调用 backtrack 函数，继续搜索下一个位置的数字。
   • 在递归完成后，需要回溯，即将当前数字从排列中移除，并标记为未使用，使其可以在其他位置被使用。
3. 最后返回结果数组。

复杂度分析

• 时间复杂度：O(n * n!)，其中 n 是 nums 的长度。主要由递归调用栈的深度决定，递归深度（即排列的数量 n!）乘以每次操作的时间复杂度 O(n)，总时间复杂度为 O(n * n!)。
• 空间复杂度：O(n * n!)，空间复杂度主要由以下几个部分组成：
  • 结果数组res 用于存储所有生成的唯一排列，在最坏情况下（所有元素都不相同），生成的排列数为 n!，因此结果数组的空间复杂度为 O(n * n!)；
  • 临时数组 track，在每个递归调用中，track 的最大长度为 n，因此其空间复杂度为 O(n)；
  • 布尔数组 used 用于标记哪些元素已经被使用，大小为 n，因此占用 O(n) 的空间。
  • 综合考虑，最主要的空间复杂度来源于结果数组 res，因此整体空间复杂度为 O(n * n!)。

代码

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
	const n = nums.length;
	let res = [];
	let used = new Array(n).fill(false);

	const backtrack = (track) => {
		if (track.length == n) {
			res.push([...track]);
			return;
		}

		for (let i = 0; i < n; i++) {
			if (used[i]) {
				continue;
			}

			// 做选择
			track.push(nums[i]);
			used[i] = true;

			// 递归
			backtrack(track);

			// 撤销选择，回溯
			track.pop();
			used[i] = false;
		}
	};

	backtrack([]);
	return res;
};

相关题目

题号	标题	题解	标签	难度
31	下一个排列	[✓]	数组 双指针
47	全排列 II	[✓]	数组 回溯
60	排列序列		递归 数学
77	组合	[✓]	回溯