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

模板题，直接套用模板，这道题我做的时候和combination那道题混淆了，这道题的每一个元素只有选和不选，没有硬性规定要选多少个，因此在递归中不应该有循环出现，而combination有个数的要求，所以需要使用循环来遍历所有可能的情况。下面给出递归解法和非递归解法，本质上都是一样的。

    
    public List<List<Integer>> subsets(int[] S) {
        List<Integer> array = new ArrayList<Integer>();
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        Arrays.sort(S);
        subsets(S, 0, array, result);
        return result;
    }
    
    public void subsets(int[] S, int beg, List<Integer> array, List<List<Integer>> result) {
        int n = S.length;
        if(beg == n) {
            result.add(new ArrayList<Integer>(array));
        }
        else {
            subsets(S, beg+1, array, result); // not chose
            array.add(S[beg]);
            subsets(S, beg+1, array, result); // chose
            array.remove(array.size() - 1);
        }
    }

    
    public List<List<Integer>> subsets(int[] S) {
        List<Integer> array = new ArrayList<Integer>();
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        
        Arrays.sort(S);
        result.add(array);
        for(int i = 0; i < S.length; i++) {
            int n = result.size();
            for(int j = 0; j < n; j++) {
                array = new ArrayList<Integer>(result.get(j));
                array.add(S[i]);
                result.add(array);
            }
        }
        
        return result;
    }