Java Solution using dp. Treat duplicated numbers as one single number


  • 0
    J

    We need to pay attention when there are duplicated elements in the sorted array.
    Up to the ith element, 'lists' actually stores all the possible sub-arrays until the last element smaller than num[i]. So this is a dp solution.
    For the array [1,2,2,2],

    when i=0; lists ={[ ]};

    when i=1; lsits ={[ ][1]}, next={[ ],[1]}+{[2],[1,2]}

    when i=2; lists ={[ ],[1]}, next={[ ],[1]}+{[2],[1,2]}+{[2,2][1,2,2]} (We treat the duplicate elements {2,2} as one single number and add it to every list in 'lists')

    when i=3; lists ={[ ],[1]} still, because num[i]==num[i-1].
    next={[ ],[1]}+{[2],[1,2]}+{[2,2][1,2,2]}+{[2,2,2],[1,2,2,2]} (Treat {2,2,2} as one number)

    public List<List<Integer>> subsetsWithDup(int[] num) {
        List<List<Integer>> lists=new ArrayList<List<Integer>>();
        lists.add(new LinkedList<Integer>());
        if(num.length==0) return lists;
        Arrays.sort(num);
        
        int dupCount=0;     
        List<List<Integer>> next=new ArrayList<List<Integer>>(lists);
        
        for(int i=0;i<num.length;i++){
            if(i!=0&&num[i]==num[i-1])  dupCount++;   //count the number of elements equal to num[i] up to now.
            else{
                dupCount=0;                     //when num[i]!=num[i-1], num[i] is a new number, reset dupCount
                next=new ArrayList<List<Integer>>(lists);             
            }
            
            for(List<Integer> list:lists){
                List<Integer> tmp=new LinkedList<Integer>(list);
                for(int count=0;count<=dupCount;count++){
                    tmp.add(num[i]);
                }
                next.add(tmp);
            }
            
            if(i==num.length-1||num[i]!=num[i+1])       
                lists=next;
        }
        return lists;
    }

Log in to reply
 

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