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] <= 10solution
和上一题不一样的点在于，这道题目的 nums 包含了重复的元素，画出递归树，我们也会发现同一层不能选择相同的元素，否则答案就会重复。
var permuteUnique = function(nums) {
let result = [];
let used = new Array(nums.length).fill(false);
dfs(used,[],nums,result);
return result;
};
function dfs(used,path,nums,result){
if(path.length === nums.length){
result.push([...path]);
return;
}
let set = new Set();
for(let i = 0; i< nums.length; i++){
if(!used[i] && !set.has(nums[i])){
path.push(nums[i]);
set.add(nums[i]);
used[i] = true;
dfs(used,path,nums,result);
path.pop();
used[i] = false;
}
}
}
当然这里的 set 也可以用数组来代替，节省空间，或者我们可以对 nums 进行排序，利用挨在一起的特性来判断，是否选到重复的元素。
但是对于这个数据规模省略这点空间用处不大。
var permuteUnique = function(nums) {
let result = [];
nums.sort((a, b) => a - b);
let used = new Array(nums.length).fill(false);
dfs(used, [], nums, result);
return result;
};
function dfs(used, path, nums, result) {
if (path.length === nums.length) {
result.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (!used[i]) {
if (i > 0 && nums[i-1] === nums[i]&& !used[i-1]) continue;
path.push(nums[i]);
used[i] = true;
dfs(used, path, nums, result);
path.pop();
used[i] = false;
}
}
}
了解 !used[i-1] 这个条件为什么是必要的，确实需要一些深入的思考。我们来分步骤解析这个逻辑，以便更清楚地理解它如何帮助防止重复排列的生成。
首先，假设我们有一个排序后的数组，如 [1, 2, 2]。关键在于如何处理这两个 2，使得它们不会在递归生成的排列中出现在相同的位置，造成重复的排列。
!used[i-1]当我们在数组中遇到连续的相同数字时，比如两个 2，我们的目标是确保在生成排列的过程中，这些相同的数字不会无谓地交换位置，导致生成重复的排列。这就是 if (i > 0 && nums[i-1] === nums[i] && !used[i-1]) continue; 这行代码的作用。
i > 0 确保我们不是在查看数组的第一个元素（因为第一个元素前面没有元素）。nums[i-1] === nums[i] 检查当前元素是否与前一个元素相同。如果是，那么我们必须谨慎处理，因为错误地处理会导致重复的排列。!used[i-1] 这是核心部分。这个条件检查前一个相同的元素是否在当前的递归路径中已经被使用。!used[i-1] 的作用假设我们没有这个条件，仅仅是 i > 0 && nums[i-1] === nums[i]。那么在某些情况下，虽然前一个相同的元素已经被使用并回溯（即已经被放回），我们仍然会跳过当前元素。这样做实际上是错误的，因为前一个元素已经不在当前递归路径中了，我们应该允许当前元素被使用，以生成新的排列。
当 !used[i-1] 为真（即 used[i-1] 为假），意味着前一个相同的元素没有被使用。这种情况通常出现在我们尝试开始一个新的递归分支，但前一个相同的元素已经被“回溯”并且放回了未使用的状态。如果我们允许当前的元素（nums[i]）在这种情况下被使用，那么它将会错误地复制一个已经生成的排列，因为这实际上是在尝试一个已经由前一个元素尝试过的排列路径。
让我们用 [1, 2, 2] 来具体化这个过程：
1，然后选择第一个 2，递归路径为 [1, 2]。2，路径变为 [1, 2, 2]。[1, 2]，然后回溯到 [1]。此时，第一个 2 被标记为未使用。!used[i-1]，我们可能会错误地跳过第二个 2 的使用，尽管此时应该尝试使用它来生成新的排列。因此，!used[i-1] 确保我们仅在前一个相同元素实际上还处在路径中时，才跳过当前元素。这是一种避免重复而且正确处理数组中连续重复元素的方法。