2015年9月30日星期三

Leetcode 90 Subsets II

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],
  []
]

Solution 1: back tracking or DFS
 public class Solution {  
   public List<List<Integer>> subsetsWithDup(int[] nums) {  
     Arrays.sort(nums);  
     List<List<Integer>> res=new ArrayList<>();  
     List<Integer> one=new ArrayList<>();  
     dfs(0,nums,one,res);  
     return res;  
   }  
   private void dfs(int d, int[] nums, List<Integer> one, List<List<Integer>> res) {  
     if (d==nums.length) res.add(new ArrayList<Integer>(one));  
     else {  
       int i=d+1;  
       while (i<nums.length && nums[i]==nums[d]) i++;  
       dfs(i,nums,one,res);//select none  
       one.add(nums[d]);//select 1+  
       dfs(d+1,nums,one,res);  
       one.remove(one.size()-1);  
     }  
   }  
 }  

没有评论:

发表评论