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

  • 0

    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;
        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.
                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++){
        return lists;

Log in to reply

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