LeetCode 47.全排列 II 是一个经典的回溯算法问题，要求生成一个包含重复数字的数组的所有不重复的全排列。与普通的全排列问题（LeetCode 46.全排列）不同，这个问题需要处理数组中的重复元素，避免生成重复的排列。
问题描述
给定一个可包含重复数字的序列nums，按任意顺序返回所有不重复的全排列。
示例
示例 1：
输入：nums = [1,1,2]
输出：[[1,1,2], [1,2,1], [2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
解题思路
• 排序：首先对数组进行排序，这样可以方便地处理重复元素。如果两个相邻的元素相同，那么在生成排列时可以跳过重复的分支。
• 回溯算法：使用回溯算法生成所有可能的排列。
• 使用一个布尔数组used来记录当前元素是否已经被使用。
• 在递归过程中，逐步构建当前排列，并在满足条件时将其加入结果列表。
• 对于重复元素，如果当前元素与前一个元素相同且前一个元素未被使用，则跳过当前分支，避免重复。
代码实现
以下是用 C++实现的完整代码：
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;class Solution {
public:vector<vector<int>> permuteUnique(vector<int>& nums) {vector<vector<int>> result;vector<int> path;vector<bool> used(nums.size(), false);// 对数组进行排序，方便处理重复元素sort(nums.begin(), nums.end());// 回溯函数function<void()> backtrack = [&]() {if (path.size() == nums.size()) {result.push_back(path);return;}for (int i = 0; i < nums.size(); ++i) {// 跳过重复元素if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {continue;}// 选择当前元素path.push_back(nums[i]);used[i] = true;// 递归backtrack();// 回溯path.pop_back();used[i] = false;}};backtrack();return result;}
};int main() {Solution solution;vector<int> nums = {1, 1, 2};vector<vector<int>> result = solution.permuteUnique(nums);for (const auto& perm : result) {for (int num : perm) {cout << num << " ";}cout << endl;}return 0;
}
代码解释
• 排序：
sort(nums.begin(), nums.end());
对数组进行排序，这样可以方便地处理重复元素。
• 回溯函数：
• 如果当前路径的长度等于数组的长度，说明已经生成了一个完整的排列，将其加入结果列表。
• 遍历数组，对于每个元素：
• 如果当前元素已经被使用，或者当前元素与前一个元素相同且前一个元素未被使用，则跳过当前分支。
• 否则，将当前元素加入路径，并标记为已使用。
• 递归调用回溯函数。
• 回溯时，移除当前元素，并标记为未使用。
• 跳过重复元素：
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {continue;}
这里有两个条件：
• 如果当前元素已经被使用，跳过。
• 如果当前元素与前一个元素相同，且前一个元素未被使用，跳过。这是因为前一个元素已经在之前的递归分支中被处理过，再处理当前元素会导致重复。
输出
对于输入[1, 1, 2]，程序的输出为：
1 1 2
1 2 1
2 1 1
时间复杂度
• 由于数组中可能有重复元素，时间复杂度为(O(n!\times n))，其中(n)是数组的长度。
• 排序的时间复杂度为(O(n\log n))，但对总时间复杂度影响较小。
空间复杂度
• 递归调用的深度为(O(n))。
• 结果列表的空间复杂度为(O(n!\times n))。
关于判断条件 !used[i - 1]
当然可以！!used[i - 1]是一个关键的条件，用于避免生成重复的排列。我们来详细解释一下这个条件的作用。
背景
在处理包含重复元素的数组时，我们需要确保生成的排列是唯一的。例如，对于数组[1, 1, 2]，我们希望生成的排列是：
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
而不是：
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
[1, 1, 2] // 重复
[1, 2, 1] // 重复
问题的核心
当数组中有重复元素时，如何避免生成重复的排列？
!used[i - 1]的作用
假设数组已经排序，例如[1, 1, 2]。在回溯算法中，我们逐个选择数组中的元素，并将其加入当前路径。为了防止重复，我们需要避免在相同层级的递归中重复选择相同的元素。
具体解释
• nums[i] == nums[i - 1]：当前元素与前一个元素相同。
• !used[i - 1]：前一个相同的元素尚未被使用。
如果这两个条件同时满足，说明当前元素是重复的，并且它的前一个相同元素还没有被使用。这意味着我们已经在之前的递归分支中处理过这个元素，因此当前分支会导致重复的排列。
举个例子
假设数组是[1, 1, 2]，排序后仍然是[1, 1, 2]。
• 第一层递归：
• 选择第一个1，路径变为[1]，标记used[0] = true。
• 递归进入下一层。
• 第二层递归：
• 选择第二个1，路径变为[1, 1]，标记used[1] = true。
• 递归进入下一层。
• 选择2，路径变为[1, 1, 2]，这是一个有效的排列。
• 回溯：
• 回到第二层，撤销选择第二个1，路径变为[1]，标记used[1] = false。
• 选择2，路径变为[1, 2]，标记used[2] = true。
• 递归进入下一层。
• 选择第二个1，路径变为[1, 2, 1]，这是一个有效的排列。
• 回到第一层：
• 撤销选择第一个1，路径为空，标记used[0] = false。
• 选择第二个1，路径变为[1]，标记used[1] = true。
• 但是此时，nums[1] == nums[0]且!used[0]，即当前元素与前一个元素相同，且前一个元素未被使用。这意味着我们已经在之前的分支中处理过这个元素，因此跳过当前分支。
• 选择2：
• 路径变为[2]，标记used[2] = true。
• 选择第一个1，路径变为[2, 1]，标记used[0] = true。
• 选择第二个1，路径变为[2, 1, 1]，这是一个有效的排列。
总结
!used[i - 1]的作用是确保在相同层级的递归中，不会重复选择相同的元素。如果当前元素与前一个元素相同，且前一个元素尚未被使用，那么当前分支会导致重复的排列，因此需要跳过。
希望这个解释清楚地说明了!used[i - 1]的作用！如果有任何疑问，欢迎继续提问。
