leetcode-有重复数字的全排列-98

题目要求

思路
1.同【没有重复项的全排列-97】这个题一样，都是递归的题，区别在于这个可能会包含重复的数字，因此，不能只是简单的通过两个值是否相等然后用标志位标记，而是新增了一个数组，这个数组专门用于存储该元素是否被使用。
2.需要特殊处理的是，类似【1，2，1】的这种的结果可能会有两个，这是因为两个1的下标不同，这时我们可以对最初的元素进行排序，如果某个元素是重复元素，并且之前已经使用过，就跳过该元素。

if(i > 0 && num[i-1] == num[i] && !vis[i-1])continue;

代码实现

class Solution {
public:vector<vector<int>> res;vector<vector<int> > permuteUnique(vector<int>& num) {sort(num.begin(), num.end());//标记vector<int> vis(num.size(), 0);vector<int> n;per(num, n, vis);return res;}void per(vector<int>& num, vector<int>& n, vector<int>& vis){if(num.size() == n.size()){res.push_back(n);return;}for(int i = 0; i < num.size(); i++){if(vis[i])continue;if(i > 0 && num[i-1] == num[i] && !vis[i-1])continue;vis[i] = 1;n.push_back(num[i]);per(num, n, vis);vis[i] = 0;n.pop_back();}}
};