Java ACCEPT solution go though the array one time.


  • 0
    S
    public List<List<Integer>> subsetsWithDup(int[] num) {
    		Arrays.sort(num);
            for(int i = 0;i < num.length;i++){
                List<List<Integer>> lst = new ArrayList<List<Integer>>();
                // copy the original list
                for(int j = 0;j < gross.size();j++){
                	List<Integer> newlst = new ArrayList<Integer>(gross.get(j));
                    lst.add(newlst);
                }
                	
                // add the new number to each sub list
                for(int j = 0;j < lst.size();j++)
                    lst.get(j).add(num[i]);
                
                // add the element itself
                List<Integer> curNum = new ArrayList<Integer>();
                curNum.add(num[i]);
                lst.add(curNum);
                
                // add the previous element conditionally
                if(!gotIt.contains(num[i])){
                    gotIt.add(num[i]);
                    for(int j = 0;j < gross.size();j++){
                    	List<Integer> newlst = new ArrayList<Integer>(gross.get(j));
                        lst.add(newlst);
                    }
                }else{
                   for(int j = 0;j < gross.size();j++){
                        boolean contain = false;
                        for(int u = 0;u < gross.get(j).size();u++)
                            if(gross.get(j).get(u) == num[i])
                                contain = true;
                        if(!contain){
                        	List<Integer> newlst = new ArrayList<Integer>(gross.get(j));
                            lst.add(newlst);
                        }
                    } 
                }
                
                // copy current list
                gross = new ArrayList<List<Integer>>(lst);
            }
            
            List<Integer> empty = new ArrayList<Integer>();
            gross.add(empty);
            return gross;
        }

Log in to reply
 

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