Java Accepted Solution go through once by inserting O(n!)


  • 1
    S

    Generate the i-th List<List<Integer>> based on the (i-1)-th List<List<Integer>> by inserting num[i] into each gap of List<integer> . Also use a hashset to mark the permutation being visited. The idea is pretty simple.

    public class Solution {
        public List<List<Integer>> permuteUnique(int[] num) {
            List<List<Integer>> opt = new ArrayList<List<Integer>>();
            
            // edge case
            if(num.length==0){return opt;}
            
            // base case
            List<Integer> firstLst = new ArrayList<Integer>();
            firstLst.add(num[0]);
            opt.add(firstLst);
            
            // iteration
            for(int i =1;i < num.length;i++){
                HashSet<List<Integer>> visited = new HashSet<List<Integer>>();
                int numOfLastOpt = opt.size();
                for(int j = 0;j < numOfLastOpt;j++){
                    // insert new int into each valid gap
                    int positions = opt.get(j).size();
                    for(int u = 0;u <= positions;u++){
                        if(u != 0){
                            if(opt.get(j).get(u-1) != num[i]){
                                List<Integer> newLst = new ArrayList<Integer>(opt.get(j));
                                newLst.add(u,num[i]);
                                if(!visited.contains(newLst)){
                                    opt.add(newLst);
                                    visited.add(newLst);
                                }
                            }
                        }else{
                            List<Integer> newLst = new ArrayList<Integer>(opt.get(j));
                            newLst.add(u,num[i]);
                            if(!visited.contains(newLst)){
                                opt.add(newLst);
                                visited.add(newLst);
                            }
                        }
                    }
                }
                // delete previous opt
                for(int j = 0;j < numOfLastOpt;j++){
                    opt.remove(0);
                }
            }
            
            return opt;
        }
    }

Log in to reply
 

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