2015年9月28日星期一

Leetcode 78 Subsets

Given a set of distinct integers, 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,3], a solution is:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution 1, also a combination problem not permutation.
 public class Solution {  
   public List<List<Integer>> subsets(int[] nums) {  
     List<List<Integer>> res=new ArrayList<>();  
     List<Integer> one=new ArrayList<>();  
     Arrays.sort(nums);  
     dfs(0,nums,one,res);  
     return res;  
   }  
   private void dfs(int d, int[]nums, List<Integer> one, List<List<Integer>> res) {  
     res.add(new ArrayList<Integer>(one));  
     for (int i=d; i<nums.length; i++) {  
       one.add(nums[i]);  
       dfs(i+1,nums,one,res);  
       one.remove(one.size()-1);  
     }  
   }  
 }  

Solution 2, another way to wring the code.
 public class Solution {  
   public List<List<Integer>> subsets(int[] nums) {  
     List<List<Integer>> res=new ArrayList<>();  
     List<Integer> one=new ArrayList<>();  
     Arrays.sort(nums);  
     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 {  
       dfs(d+1,nums,one,res);  
       one.add(nums[d]);  
       dfs(d+1,nums,one,res);  
       one.remove(one.size()-1);  
     }  
   }  
 }  

没有评论:

发表评论