leetcode47 全排列（去重问题）

这道题相对于leetcode46多了一个去重操作。在代码上也就是在往保存的vector里push进元素的时候多了这么一行判断

if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) { continue; }

即当vis[i] = 0时，有两种情况： 1。后面的不成立，即没有被访问过的时候，会先访问它 2。这种情况就是在回溯到底的时候，即栈中没有元素，需要另取一个元素来作为第一个元素形成新的排列时，此时我们要保证这个元素和前一个元素不一样，所以就有这一个判断nums[i] == nums[i - 1]，但是这个也很有可能是 不是作为第一个元素的时候的一个排列，所以用!vis[i - 1]来保证回溯到底的情况（因为此时所有元素的vis都已经变成0了） 3。 对了，还要对输入的数组进行一个排序，这样相同的元素才能在一起，才可以根据是否和前面元素一样来判断是否是重复的元素

class Solution { private: vector<vector<int>> result; vector<bool> used; //这个函数的意义是：检测index处的数字的序列 void findPermute(vector<int>& nums, int index, vector<int>& saveArray){ if( index == nums.size()){ result.emplace_back(saveArray); return ; } for(int i = 0 ; i < nums.size(); i++) { if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) { //没有访问过 但是和前面的元素是一样的 并且前面元素没访问过 continue; } saveArray.push_back(nums[i]); used[i] = true; findPermute(nums, index + 1, saveArray); used[i] = false; saveArray.pop_back(); } } public: vector<vector<int>> permuteUnique(vector<int>& nums) { result.clear(); if(nums.size() == 0) return result; sort(nums.begin(), nums.end()); vector<int> saveArray; used = vector<bool>(nums.size(), false); findPermute(nums, 0, saveArray); return result; } };