# 47. Permutations II

## Description

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]
]


## Analysis

4!


1.如果当前元素已经被使用过，则在当前循环中应该被跳过

2.如果当前元素在之前出现过，且前一个元素还没有被使用过，则也应当被跳过。

2.对于需要跳过的元素，其判断依据为:

## code

class Solution {
void backtracking(vector<vector<int>> & res,vector<int> & templist,vector<int> & nums,bool * used){
if(templist.size()==nums.size()){
res.push_back(templist);
return;
}
for(int i=0;i<nums.size();++i){
if(used[i]||i>0&&nums[i]==nums[i-1]&&!used[i-1])     continue;
used[i]=true;
templist.push_back(nums[i]);
backtracking(res,templist,nums,used);
used[i]=false;
templist.pop_back();
}
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
bool used[nums.size()]={false};
vector<vector<int>> res;
vector<int> templist;
sort(nums.begin(),nums.end());
backtracking(res,templist,nums,used);
return res;
}
};
`

### 学籍管理系统文档

#### 北邮教务系统评教脚本

Published on September 17, 2017

#### 72.Edit distance

Published on September 17, 2017