Subsets

Problem

Given a set of distinct integers, return all possible subsets.

Notice

Elements in a subset must be in non-descending order.

The solution set must not contain duplicate subsets.

Example

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

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

Challenge

Can you do it in both recursively and iteratively?

Solution

class Solution {    public ArrayList
    
     
      > subsets(int[] nums) {        ArrayList
      
       
        > res = new ArrayList<>();        if (nums == null || nums.length == 0) return res;        ArrayList
        
          cur = new ArrayList<>();        Arrays.sort(nums);        dfs(nums, cur, res, 0);        return res;    }    public void dfs(int[] nums, ArrayList
         
           cur, ArrayList
          
           
            > res, int index) { if (index > nums.length) return; res.add(new ArrayList
            
              (cur)); for (int i = index; i < nums.length; i++) { cur.add(nums[i]); dfs(nums, cur, res, i+1); cur.remove(cur.size()-1); } }}
            
           
          
         
        
       
      
     
    

Subsets II

Problem

Given a list of numbers that may has duplicate numbers, return all possible subsets

##Notice

Each element in a subset must be in non-descending order.

The ordering between two subsets is free.The solution set must not contain duplicate subsets.Have you met this question in a real interview? Yes

Example

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

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

Challenge

Can you do it in both recursively and iteratively?

Solution

class Solution {    public ArrayList
    
     
      > subsetsWithDup(ArrayList
      
        S) {        ArrayList
       
        
         > res = new ArrayList<>();        Collections.sort(S);        ArrayList
         
           cur = new ArrayList<>(); dfs(S, cur, res, 0); return res; } public void dfs(ArrayList
          
            S, ArrayList
           
             cur, ArrayList
            
             
              > res, int index) { if (index > S.size()) return; res.add(new ArrayList
              
                (cur)); for (int i = index; i < S.size(); i++) { if (i != index && S.get(i) == S.get(i-1)) continue; cur.add(S.get(i)); dfs(S, cur, res, i+1); cur.remove(cur.size()-1); } }}