Given a collection of integers that might contain duplicates, S, return all possible subsets.
Note:
For example,
If S = [1,2,2], a solution is:
[ [2], [1], [1,2,2], [2,2], [1,2], [] ]
public class Solution { public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) { // Start typing your Java solution below // DO NOT write main() function ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>> (); if(num == null || num.length ==0 ) return result; Arrays.sort(num); HashSet<ArrayList<Integer>> set = new HashSet<ArrayList<Integer>>(); recursion(set,new ArrayList<Integer>(),num,0); return new ArrayList<ArrayList<Integer>>(set); } public void recursion(HashSet<ArrayList<Integer>> set,ArrayList<Integer> temp, int[] num, int start){ if(set.contains(temp)){ return; }else{ set.add(temp); for(int i = start; i< num.length ; i++){ ArrayList<Integer> list = new ArrayList<Integer>(temp); list.add(num[i]); recursion(set,list,num,i+1); } } } }
public class Solution {
public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> re=new ArrayList<Integer>();
Arrays.sort(num);
results.add(re);
helper(results,re,0,num);
return results;
}
public void helper(ArrayList<ArrayList<Integer>> results, ArrayList<Integer> re, int start, int[] num){
if(start==num.length) return;
for(int i=start;i<num.length;i++){
re.add(num[i]);
ArrayList<Integer> l=new ArrayList<Integer>();
for(int j=0;j<re.size();j++)
l.add(re.get(j));
results.add(l);
helper(results,re,i+1,num);
re.remove(re.size()-1);
//to avoid repetition eg. 1,2,3,3,3
while(i<num.length-1&&num[i]==num[i+1]) i++;
}
}