46. Permutations

🟠   🔖  数组 回溯  🔗 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. 最后返回结果数组。

代码

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

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

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

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

			// 递归
			backtrack(permu);

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

	backtrack([]);
	return res;
};

相关题目

相关题目

• 31. 下一个排列
• 47. 全排列 II
• 60. 排列序列
• 77. 组合

- [31. 下一个排列](https://leetcode.com/problems/next-permutation)
- [47. 全排列 II](https://leetcode.com/problems/permutations-ii)
- [60. 排列序列](https://leetcode.com/problems/permutation-sequence)
- [77. 组合](https://leetcode.com/problems/combinations)