Subsets & Subsets II

Subsets

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

Subsets II

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

Naive Way:尝试根据2的子集写3的子集得出结论：将3加入之前每一个子集中形成新的子集，然后原来的子集不动也加入。如果遇到重复的怎么办。可以将他们逐次当成一个整体加入上一级，这样不用HashSet。
可以是recursive的，也可以是iterative的不断更新当前list。

这是iterative的，算法复杂度是O(2^n)，space也是O(2^n)。

public class Solution {
    public List<List<Integer>> subsets(int[] S) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        List<Integer> zero = new ArrayList<Integer>();
        list.add(zero);
        Arrays.sort(S);
        for(int i=0,j=1;i < S.length;i+=j){
            int k = list.size();
            j = 1;
            while(i+j < S.length && S[i+j]==S[i]) j++; // j = # of consecutive numbers
            for(int t = 1;t <= j;t++){ // consecutive numbers
                for(int u = 0;u < k;u++){ // loop previous list
                    List<Integer> sub = new ArrayList<Integer>(list.get(u));
                    for(int num = 0;num < t;num++) sub.add(S[i]);
                    list.add(sub);
                }
            }
        }
        return list;
    }
}


这是recursive的， 算法复杂度同。

public class Solution {
    public List<List<Integer>> subsets(int[] S) {
        Arrays.sort(S);
        return subsets(S, S.length-1);
    }
    
    private List<List<Integer>> subsets(int[] S, int index){
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        // base case
        if(index < 0){
            List<Integer> zero = new ArrayList<Integer>();
            list.add(zero);
            return list;
        }
        // recursive
        int j =1; // j = # of consecutive numbers 
        while(index-j >= 0 && S[index-j]==S[index]) j++;
        list = subsets(S, index-j);
        int k = list.size();
        for(int t = 1;t <= j;t++){ // consecutive numbers 
            for(int i = 0;i < k;i++){// loop previous list 
                List<Integer> sub = new ArrayList<Integer>(list.get(i));
                for(int num = 0;num < t;num++) sub.add(S[index]);
                list.add(sub);
            }
        }
        return list;
    }
}