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


  • 0
    H
    public class Solution {
        public List<List<Integer>> permuteUnique(int[] num) {
            List<List<Integer>> result=new ArrayList();
            if(num==null||num.length==0){
                return result;
            }
            result.add(new ArrayList<Integer>());
            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){
                cache.add(curPerm);
                return;
            }
            
            if(counter>0){
                List<Integer> temp=new ArrayList(curPerm);
                temp.add(cur);
                generatePermutation(onePermutation, listIndex, cache, cur, counter-1, temp);
            }
            
            if(listIndex<onePermutation.size()){
                List<Integer> temp=new ArrayList(curPerm);
                temp.add(onePermutation.get(listIndex));
                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.


  • 10
    R

    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) {
    		results.add(new ArrayList<Integer>(res));
    		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
    		res.add(num[i]);
    		isUsed[i] = true;
    		doPermutation(num);
    		isUsed[i] = false;
    		res.remove(res.size() - 1);
    	}
    } 
    }

  • 0
    Z

    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){
                result.add(new ArrayList<Integer>(cur));
                return;
            }
    
            for(Map.Entry<Integer, Integer> e: map.entrySet()) {
                if(e.getValue() == 0)
                    continue;
    
                map.put(e.getKey(), e.getValue() - 1);
                cur.add(e.getKey());
    
                permuteUnique(map, cur, result, total);
    
                map.put(e.getKey(), e.getValue() + 1);
                cur.remove(cur.size() - 1);
            }
        }
    }

  • 0
    S

    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?


  • 0
    S

    +now it gives time out...


  • 0
    S

    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.


  • 0
    H

    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){
                res.add(cur);
                return;
            }
            for(int[] entry: cache){
                if(entry[1]>0){
                    List<Integer> next=new ArrayList<Integer>(cur);
                    next.add(entry[0]);
                    entry[1]--;
                    allPermu(cache, len-1, res, next);
                    entry[1]++;
                }
            }
        }
    }

  • 0
    S

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


  • 0
    R

    I think it is already there


  • 1
    F

    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);
            res.add(row);
            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];
    }

Log in to reply
 

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