Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example, [1,1,2] have the following unique permutations:
[ [1,1,2], [1,2,1], [2,1,1] ]Subscribe to see which companies asked this question
运用set来保证每一级不会有重复的，但完成某一级的时候需要clear
static int m[100]; class Solution { public: void backtrack(vector<int>& nums,int t,vector<set<int>>&lim,vector<vector<int>>&ans, vector<int> temp) { if(t==nums.size()) { ans.push_back(temp); return ; } else { for(int i=0;i<nums.size();++i) { if(m[i]==0&&lim[t].find(nums[i])==lim[t].end()) { m[i]=1; { temp.push_back(nums[i]); lim[t].insert(nums[i]); backtrack(nums,t+1,lim,ans,temp); temp.pop_back(); m[i]=0; } } } lim[t].clear(); return ; } } vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> ans; vector<int> temp; vector<set<int>> lim(nums.size(),set<int>()); int t=0; for(int i=0;i<nums.size();++i) { if(lim[t].find(nums[i])==lim[t].end()) { m[i]=1; temp.push_back(nums[i]); lim[t].insert(nums[i]); backtrack(nums,t+1,lim,ans,temp); temp.pop_back(); m[i]=0; } } lim[t].clear(); return ans; } };