首页 > 代码库 > Subsets II

Subsets II

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.

For example,
If S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] num) {
        Arrays.sort(num);
        List<List<Integer>> result=new LinkedList<List<Integer>>();
        LinkedList<Integer> subset=new LinkedList<Integer>();
        if(num==null) return result;
        result.add(subset);
        getSubset(num,0,subset,result);
        HashSet set=new HashSet(result);
        result.clear();
        result.addAll(set);
        return result;
    }
    public void getSubset(int []num,int begin,LinkedList<Integer> subset,List<List<Integer>> result){
        if(begin==num.length){
            return;
        }
        for(int i=begin;i<num.length;i++){
            subset.add(num[i]);
            LinkedList<Integer> list=new LinkedList<Integer>();
            list.addAll(subset);
            result.add(list);
            getSubset(num,i+1,subset,result);
            subset.pollLast();
        }
    }
}