Leetcode 47. Permutations II

47. Permutations II

Total Accepted: 80610
Total Submissions: 277081
Difficulty: Medium

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,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

思路：回溯法，和类似，但是本题的元素是可以有重复的，所以处理上有所不同。具体做法是先排序，然后0到nums.size()-1的位置上，每个位置放入当前剩下元素的每个类别。

例如对于[1,2,1]，排序后为[1,1,2]，有2类数。

第一次递归形成[1]（下次递归还有2类数）和[2]（下次递归只有1类数）；

第二次递归形成[1,1]（下次递归还有1类数） [1,2]（下次递归还有1类数）和[2,1]（下次递归还有1类数）；

第三次递归形成[1,1,2] [1,2,1] [2,1,1]

代码：

 1 class Solution {
 2 public:
 3     void permuteUnique(vector<vector<int> > &res,vector<int> nums,vector<int> v,int cur){
 4         if(!nums.size()){
 5             res.push_back(v);
 6             return;
 7         }
 8         //每个位置，每个种类的数只能放一次
 9         for(int i=0;i<nums.size();i++){
10             int temp=nums[i];
11             v.push_back(temp);
12             nums.erase(nums.begin()+i);
13             permuteUnique(res,nums,v,cur+1);
14             nums.insert(nums.begin()+i,temp);
15             v.pop_back();
16             while(i+1<nums.size()&&nums[i]==nums[i+1]) i++;
17         }
18     }
19     vector<vector<int> > permuteUnique(vector<int>& nums) {
20         vector<vector<int> > res;
21         vector<int> v;
22         sort(nums.begin(),nums.end());
23         permuteUnique(res,nums,v,0);
24         return res;
25     }
26 };