LeetCode: Subset I&II

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

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

Solution:

For S=[1,2,3] only two possibilities: A subset contains S[0] or A subset doesn't contain S[0]

Caution should be exercised when using ArrayList

Note1: [] is dealt with separately
Note2: firstly used S[i] = S[i+1]. Wrong. The length of S has not be reduced by 1 thus affects the next recursive computation.
Note3: forgot to new an ArrayList<Integer> object. It's wrongto use ArrayList<Integer> withElement = sol.

public class Solution {
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        
        if(S == null || S.length == 0) return ret;
        
        ret = subsetsRec(S);
        
        ret.add(new ArrayList<Integer>());////////Note1
        
        return ret;
        
    }
    
    
    public ArrayList<ArrayList<Integer>> subsetsRec(int[] S) {
        
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        
        if(S.length==1){
            ArrayList<Integer> element = new ArrayList<Integer>();
            element.add(S[0]);
            ret.add(element);
            return ret;
        }
        
        Arrays.sort(S);
        int curInt = S[0];
        ArrayList<Integer> cur = new ArrayList<Integer>();
        cur.add(curInt);
        ret.add(cur);
        
        int[] nextS = new int[S.length-1];
        for(int i=0; i<S.length-1; i++)
        {
            nextS[i] = S[i+1];/////////////Note2
        }
        
        
        for(ArrayList<Integer> sol : subsetsRec(nextS)){
            ret.add(sol);
            ArrayList<Integer> withElement = new ArrayList<Integer>();/////////Note3
            withElement.addAll(sol);
            withElement.add(0, curInt);
            ret.add(withElement);
        }
    
        return ret;
    }
}  
 

Inspired by the discussion, I came up with the following pretty solution:

set [a,b,c], write the binary numbers of length 3.
000    []
001    [a]
010    [b]
011    [ab]
100    [c]
101    [ac]
110    [bc]
111    [abc]

SubsetII

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

Solution:

When adding a subset, see whether a same one has already been contained in the result. Only need to add code at three places to solve this:

         if(!ret.contains(cur))

            ret.add(cur);