Friday, May 27, 2016

Subsets II -- Leetcode

Question:
Given a collection of integers that might contain duplicates, nums, 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 nums = [1,2,2], a solution is:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Answer:
public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<Integer> subres = new ArrayList<Integer>();
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int len = nums.length;
        if(len==0)return res;
       
        Arrays.sort(nums);
        DFS(res, subres, 0, nums);
        return res;
    }
   
    public void DFS(List<List<Integer>> res, List<Integer> subres, int index, int[] nums){
        List<Integer> newsubres = new ArrayList<Integer>(subres);
        res.add(newsubres);
        if(index >= nums.length){
            return;
        }
       
        for(int i=index; i<nums.length; ++i){
            //Avoid duplicate set!
            if(i!=index && nums[i]==nums[i-1]){
                continue;
            }
            subres.add(nums[i]);
            DFS(res, subres, i+1, nums);
            subres.remove(subres.size()-1);
        }
        return;
    }
}

No comments:

Post a Comment