# Share my Java solution. Similar to the "Generate Parentheses" problem.

• ``````public class Solution {
public List<List<Integer>> permuteUnique(int[] num) {
List<List<Integer>> result=new ArrayList();
if(num==null||num.length==0){
return result;
}
List<List<Integer>> cache=new ArrayList();
Arrays.sort(num);
int counter=0;
int cur;
for(int i=0; i<num.length; i++){
cur=num[i];
counter++;
if(i==num.length-1||cur!=num[i+1]){
generatePermutation(result, cache, cur, counter);
counter=0;
result=cache;
cache=new ArrayList();
}
}
return result;
}

private void generatePermutation(List<List<Integer>> result, List<List<Integer>> cache, int cur, int counter){
for(List<Integer> temp: result){
generatePermutation(temp, 0, cache, cur, counter, new ArrayList<Integer>());
}
}

private void generatePermutation(List<Integer> onePermutation, int listIndex, List<List<Integer>> cache, int cur, int counter, List<Integer> curPerm){
if(listIndex==onePermutation.size()&&counter==0){
return;
}

if(counter>0){
List<Integer> temp=new ArrayList(curPerm);
generatePermutation(onePermutation, listIndex, cache, cur, counter-1, temp);
}

if(listIndex<onePermutation.size()){
List<Integer> temp=new ArrayList(curPerm);
generatePermutation(onePermutation, listIndex+1, cache, cur, counter, temp);
}
}
}
``````

I generate the result by adding elements one by one. Just like generate sets. I process the same elems together. By combining them with already exist permutations, I get what I want.
I think my coding style is not good. Please give suggestions to help me improve it. Thanks.

• Another java solution with DFS idea.

``````public class Solution {
boolean[] isUsed;
int length;
List<List<Integer>> results;
List<Integer> res;

public List<List<Integer>> permuteUnique(int[] num) {
length = num.length;
res = new ArrayList<Integer>();
results = new ArrayList<List<Integer>>();
isUsed = new boolean[length];
Arrays.sort(num);//Not needed for Permutation I
doPermutation(num);
return results;
}

public void doPermutation(int[] num) {

if (res.size() == length) {
return;
}

for (int i = 0; i < length; i++) {
if (isUsed[i])
continue;
if (i>0&&num[i]==num[i-1]&&(!isUsed[i-1]))//Not needed for Permutation I
continue;//Not needed for Permutation I
isUsed[i] = true;
doPermutation(num);
isUsed[i] = false;
res.remove(res.size() - 1);
}
}
}``````

• Another Java solution. But here I use mapping entry -> counter. No sorting is needed.

``````public class Solution {
public List<List<Integer>> permuteUnique(int[] num) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
Map<Integer, Integer> map = new HashMap<Integer, Integer>();

populate(map, num);
permuteUnique(map, new ArrayList<Integer>(), result, num.length);

return result;
}

private void populate(Map<Integer, Integer> map, int[] num) {
for(int n: num) {
if(map.containsKey(n))
map.put(n, map.get(n) + 1);
else
map.put(n, 1);
}
}

private void permuteUnique(
Map<Integer, Integer> map, List<Integer> cur,
List<List<Integer>> result, int total) {
if(cur.size() == total){
return;
}

for(Map.Entry<Integer, Integer> e: map.entrySet()) {
if(e.getValue() == 0)
continue;

map.put(e.getKey(), e.getValue() - 1);

permuteUnique(map, cur, result, total);

map.put(e.getKey(), e.getValue() + 1);
cur.remove(cur.size() - 1);
}
}
}``````

• Hi! Your solution is very nice, however I don't understand what is the purpose of the boolean array isUsed? Isn't it enough just to do the check if (i>0&&num[i]==num[i-1])? Why we need to mark elements that we have used?

• +now it gives time out...

• Nice!

@SamMy89 - The boolean array is needed to check whether the element is used or not > This helps to avoid several operations (iterations and recursions).

For example: in an array (after sorting) > [1,1,1,1,1,1,1,2,3,4] with isUsed array values being [T,T,T,T,T,F,T,F,F,F] :

If the execution continues without this check, it will result in another list like [1,1,1,1,1,1,1,2,3,4] which is of no use to us as we need just unique lists. This check avoids creating such duplicate lists and does not TLE.

• Another solution, I think is better than my previous one and it is similar with the second one.

``````public class Solution {
public List<List<Integer>> permuteUnique(int[] num) {
List<List<Integer>> res=new ArrayList<List<Integer>>();
HashMap<Integer, Integer> cluster=new HashMap<Integer, Integer>();
//Count every number.
for(int i: num){
if(!cluster.containsKey(i)){
cluster.put(i, 0);
}
int counter=cluster.get(i)+1;
cluster.put(i, counter);
}
int[][] cache=new int[cluster.size()][2];
int counter=0;
for(Map.Entry<Integer, Integer> e: cluster.entrySet()){
cache[counter][0]=e.getKey();
cache[counter][1]=e.getValue();
counter++;
}
allPermu(cache, num.length, res, new ArrayList<Integer>());
return res;
}
private void allPermu(int[][] cache, int len, List<List<Integer>> res, List<Integer> cur){
//Do a DFS here.
if(len==0){
return;
}
for(int[] entry: cache){
if(entry[1]>0){
List<Integer> next=new ArrayList<Integer>(cur);
entry[1]--;
allPermu(cache, len-1, res, next);
entry[1]++;
}
}
}
}``````

• Hi, I see your solution named DFS. Can you explain a little detail about how DFS is used?

• I think it is already there

• My solution tries to improve from permutation 1 to get the answer for permutation 2. The only thing we need to do is skipping when there is a duplicate of current element found in previous sequence.

``````public List<List<Integer>> permuteUnique(int[] num) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if (num == null || num.length == 0) return res;
Arrays.sort(num);
permute(num, 0, res);
return res;
}

public void permute(int[] num, int level, List<List<Integer>> res) {
if (level == num.length) {
List<Integer> row = new ArrayList<Integer>();
for (int a : num) row.add(a);
return;
}
for (int i = level; i < num.length; i++) {
// skip if we found duplicate
boolean skip = false;
for(int j = level; j < i; j++) {
if(num[j] == num[i]) {
skip = true;
break;
}
}
if (skip) continue;
swap(num, level, i);
permute(num, level + 1, res);
swap(num, level, i); // reset
}
}

public void swap(int[] num, int i, int j) {
if (i == j) return;
num[i] = num[j] - num[i];
num[j] = num[j] - num[i];
num[i] = num[j] + num[i];
}``````

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