### leetcode Question 70: Permutations II

Permutations II

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

Analysis:
Facing this kind of problem, just consider this is a similar one to the previous(see here), but need some modifications. In this problem, what we need it to cut some of the subtrees.  e.g. 122
122
/             |           \
122          212         X  (here because 2=2, we don't need to swap again)
/     \          /    \
122   X     212 221

So, if there exist same element after current swap, there there is no need to swap again.
Details see code.

Code:
class Solution {
public:
bool noswap(int k, int i, const vector<int> num){
for (int j=k;j<i;j++){
if (num[j]==num[i]){
return true;
}
}
return false;
}

void perm(vector<int> num,int k,int n, vector<vector<int> > &res){
if (k==n){
res.push_back(num);
}else{
for (int i=k;i<=n;i++){

if (noswap(k,i,num)){continue;}

int tmp = num[k];
num[k]=num[i];
num[i]=tmp;

perm(num,k+1,n,res);

tmp = num[k];
num[k]=num[i];
num[i]=tmp;
}
}
}
vector<vector<int> > permuteUnique(vector<int> &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<vector<int> > res;
perm(num,0,(num.size()-1),res);
return res;
}
};


1. noswap 函数写得很棒，就是不知道为什么要这么写？

1. 这实际上是检查k到i以前有没有和num[i]相同的值。其实不这么写也行，可以用hash set来判重，效率会更高些。

2. 用hashset反而效率变低了 是为什么呢

2. 如果数列的重复个数大于2，例如数列 1，2，2，2就不对了

1. package com.company;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Solution {

public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.permuteUnique(new int[]{1, 2, 2, 2}));
}

private boolean noswap(int k, int i, int[] num){
for (int j=k;j> res){
if (k==n){
}else{
for (int i=k;i<=n;i++){

if (noswap(k,i,num)){continue;}

int tmp = num[k];
num[k]= num[i];
num[i] =tmp;

perm(num,k+1,n,res);

tmp = num[k];
num[k]= num[i];
num[i] = tmp;
}
}
}
public List> permuteUnique(int[] nums) {
// Start typing your C/C++ solution below
// DO NOT write int main() function