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

• 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>>();
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){
for(int count=0;count<=dupCount;count++){