47. 全排列 II

题目

给定一个可包含重复数字的序列 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]]

提示：

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

思路

        为了得到不重复的所有排列组合，我们对输入数组进行排序，让相同的元素相邻排列，这样在后续的回溯过程中，能更方便地判断和避免重复排列。然后创建一个标记数组visit，看这个数字是否已被使用，保证每个元素在一个排列中仅使用一次。在hs中，将未使用的元素添加到当前排列中，然后在检查元素是否已被使用，还会检查当前元素是否和前一个元素相同，并且前一个元素未被使用。如果满足这个条件，就跳过当前元素，避免生成重复排列。在递归调用结束后，将元素标记为未使用，并从当前排列中移除该元素，这样就可以尝试其他可能的排列。 

代码

class Solution {
public:vector<int> visit;//用来标记访问过的数void hs(vector<int>& nums,vector<vector<int>>& res,int index,vector<int>& n){if (index==nums.size())//n里面已经把nums里所有的数字都填充进来了{res.emplace_back(n);return;}for(int i=0;i<nums.size();i++) {//当前数字已被访问过或当前数字与前一个数字大小相等并且前一个数字未被访问if (visit[i]||(i>0&&nums[i]==nums[i-1]&&!visit[i - 1])){continue;//跳过当前循环，进入下一层}n.emplace_back(nums[i]);//符合条件，放入nvisit[i]=1;//把当前数字标记为已访问hs(nums,res,index+1,n);//从下一个数开始进行递归visit[i] = 0;//把当前数字标记为未访问并从n中移除，尝试其他排列n.pop_back();}}vector<vector<int>> permuteUnique(vector<int>& nums) {vector<vector<int>> res;//结果数组vector<int> n;//存每种组合的数组visit.resize(nums.size());//把visit数组的大小调整成nums数组的大小sort(nums.begin(),nums.end());//对nums排序，方便把重复的数字放在一起hs(nums,res,0,n);//递归进行全排列return res;}
};