47. Permutations II

47. Permutations IIopen in new window

🟠 🔖 数组 回溯 🔗 LeetCodeopen in new window

题目

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
[1,2,1],
[2,1,1]]

Example 2:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Constraints:

1 <= nums.length <= 8
-10 <= nums[i] <= 10

题目大意

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

解题思路

可以使用回溯算法生成全排列，同时处理数组中可能存在重复元素的情况：

定义一个结果数组 res，一个路径数组 track 用于记录当前排列的路径，以及一个布尔数组 used 用于标记某个元素是否已经被使用过。
对输入数组 nums 进行升序排序，以方便在后续去重的过程中判断相邻元素是否相同。
创建一个名为 backtrack 的递归函数，该函数用于生成全排列。函数没有参数，通过数组 track 和布尔数组 used 记录当前的路径和状态。
在 backtrack 函数中，首先检查当前路径的长度是否等于输入数组 nums 的长度，如果是，则说明已经生成了一个完整的排列，将当前路径加入到结果数组 res 中，并直接返回。
然后，从头开始遍历排序后的数组 nums，对于每个元素：
- 如果该元素已经被使用过 (used[i] 为 true)，则跳过当前元素。
- 如果该元素和前一个元素相同，且前一个元素没有被使用过 (!used[i - 1])，则跳过当前元素。这是为了避免生成重复的排列，确保相同元素只在同一层递归中出现一次。
- 否则，将当前元素加入到路径 track 中，标记该元素为已使用，递归调用 backtrack 函数，进入下一层，并在递归调用结束后，将当前元素从路径中弹出，标记为未使用，以便回溯到上一层，继续遍历其他元素。
最后，返回结果数组 res，其中包含了所有满足条件的全排列。

标准全排列算法之所以出现重复，是因为把相同元素形成的排列序列视为不同的序列，但实际上它们应该是相同的；而如果固定相同元素形成的序列顺序，保证相同元素在排列中的相对位置保持不变，就避免了重复。

代码

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

	// 先排序，让相同的元素靠在一起
	nums.sort((a, b) => a - b);

	const backtrack = () => {
		if (track.length == nums.length) {
			res.push([...track]);
			return;
		}
		for (let i = 0; i < nums.length; i++) {
			// 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
			if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
				continue;
			}
			track.push(nums[i]);
			used[i] = true;
			backtrack(i + 1);
			track.pop();
			used[i] = false;
		}
	};

	backtrack();
	return res;
};

47. Permutations II

# 47. Permutations IIopen in new window

# 题目

# 题目大意

# 解题思路

# 代码

# 相关题目

47. Permutations IIopen in new window

题目

题目大意

解题思路

代码

相关题目