LeetCode47. 全排列 II

题目

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

分析

本题是在 LeetCode46. 全排列 基础上的变形，就是加上序列中包含重复数字这一条件，导致的结果就是可能出现重复的序列。此题又回归到如何去重的问题？

1.排序 + used 数组见 LeetCode40. 组合总和 II

2. 不可排序，用set进行哈希pass。当然如果数据元素的范围小的话，可以直接用数组进行哈希。见 LeetCode491. 递增子序列

仔细看在 LeetCode求组合总和、求子集问题

代码

sort + used 数组（记录是否使用过）去重

 1 class Solution {
 2 public:
 3     vector<int>path;
 4     vector<vector<int>>res;
 5     void backtracking(vector<int>nums,vector<bool>used){
 6         if(path.size() == nums.size()){
 7             res.push_back(path);
 8             return;
 9         }
10         
11         for(int i = 0;i < nums.size();i++){
12             if(i > 0 && nums[i] == nums[i-1] && used[i-1] == false) continue;
13             if(used[i] == false){
14                 used[i] = true;
15                 path.push_back(nums[i]);
16                 backtracking(nums,used);
17                 used[i] = false;
18                 path.pop_back();
19             }
20         }
21     }
22     vector<vector<int>> permuteUnique(vector<int>& nums) {
23         sort(nums.begin(),nums.end());
24         vector<bool>used(nums.size(),false);
25         backtracking(nums,used);
26         return res;
27     }
28 };

上述代码12行 false改为 true也对

树层上去重 used[i - 1] == false

树枝上去重 used[i - 1] == true

哈希去重

 1 class Solution {
 2 public:
 3     vector<int>path;
 4     vector<vector<int>>res;
 5     void backtracking(vector<int>nums,vector<bool>used){
 6         if(path.size() == nums.size()){
 7             res.push_back(path);
 8             return;
 9         }
10         int u[21] = {0};  //用来去重
11         for(int i = 0;i < nums.size();i++){
12             if(u[nums[i] + 10] || used[i]) continue;
13             u[nums[i] + 10] = 1;
14             used[i] = 1;
15             path.push_back(nums[i]);
16             backtracking(nums,used);
17             used[i] = 0;
18             path.pop_back();
19         }
20     }
21     vector<vector<int>> permuteUnique(vector<int>& nums) {
22         vector<bool>used(nums.size(),false);
23         backtracking(nums,used);
24         return res;
25     }
26 };

关键代码

if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { 
    continue;
}

int u[21] = {0};  //用来去重
         for(int i = 0;i < nums.size();i++){
             if(u[nums[i] + 10] || used[i]) continue;

补充：对于全排列问题用sort+used去重，对树枝去重，和树层间去重效果一样，但树枝去重效率不高，还是用树层去重好