Only for Share 【java accepted】

• I got TEL first by removing the duplication after it has generated the duplication. Then, I change my mind,
If we can avoid generating the duplication, will the method be faster. Keep this in mind, here is my algorithm. I first sort the input array, then by recursive algorithm permute the array, but each unique number only permute once. the code is here:

``````/**
* Given a collection of numbers, return all possible permutations.
* @param num
* @return
* @author huangting
* @date 2014-7-1
*/
private List<List<Integer>> permute(int[] num) {
//because we have to delete from the array, so we first transfer
for(int i=0;i<num.length;i++){
}
return permuteDetail(n);
}
/**
* by recursive algorithm, I do the permutation
* @param num
* @return
* @author huangting
* @date 2014-7-1
*/
List<List<Integer>> ret = new ArrayList<List<Integer>>();
if(num == null || num.size()<=0)
return ret;
if(num.size() == 1){
ArrayList<Integer> curr = new ArrayList<Integer>();
return ret;
}
int last = Integer.MAX_VALUE;
for(int i=0;i<num.size();i++){
//since we have sort the array, if the next one is the same with the last
//one, it will get the same permutation, so we don't need to permute it
if(num.get(i) == last)
{
continue;
}
//track the last one num
last = num.get(i);
int cur = num.get(i);

last = newNum.get(i);
newNum.remove(i);
List<List<Integer>> sub = permuteDetail(newNum);
//merge
for(int j=0;j<sub.size();j++){
}
}
return ret;
}
public List<List<Integer>> permuteUnique(int[] num) {
Arrays.sort(num);//first sort,so we can avoid the duplication by not generating it
return permute(num);
}``````

• I have a more elegant code which is change from permutation I to permutation II.But maybe the method to remove duplicated is not so efficient.I think hashtable will be change the satuation.

``````class Solution {
public:
//why output limit exceed!!!???can't find the reason!!!
vector<vector<int> > ans;
vector<vector<int> > permuteUnique(vector<int> &num) {
sort(num.begin(),num.end());
dfs(num,0);
return ans;
}
void dfs(vector<int> &num,int start) {
//step 1
if(start == num.size()) {
ans.push_back(num);
return;
}
//step 2

//step 3
for(int i = start;i < num.size();i++) {
//skip duplicate,if the element have emerge before,skip this one!!!
bool skip = false;
for(int j = start;j < i;j++) {
if(num[j] == num[i]) {
skip = true;
break;
}
}
if(skip)
continue;
//if before have be meeted,so skip this???maybe hashtable will be more efficient???
swap(num[i],num[start]);
dfs(num,start+1);
swap(num[i],num[start]);
}
}
``````

};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.