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

Solutions1：DFS，recursion

这道题是要求生成所有子集，那么首先我们有一个能返回所有子集的ArrayList res, 和一个临时变量ArrayList tmp, 当tmp满足一定条件的时候，往res里面添加结果

Subset这道题的条件比较直观，就是每当我们添加了一个元素，都是一个新的子集。用一个int start来记录此子集的起点在哪，比如当start = 1的时候就是从第二个元素往后循环添加元素（0 base）,每次当此层用了第i个元素，那么下一层需要传入下一个元素的位置i+1 除此之外，当循环结束要返回上一层dfs的时候我们需要把这一层刚添加元素删去。

比如输入集合为［1，2，3］应当是这么运行，

[]

[1]

[1,2]

[1,2,3] //最底层子循环到头返回删去3，上一层的子循环也到头删去2

          //而此时，这一层循环刚到2，删去后还可以添加一个3

[1,3] //删除3，删除1

[2]

[2,3] //删除3，删除2

[3]

几点注意的地方

1. 结果要求生成升序排列，所以最开始的时候我们需要Sort一下

2. 往res里面添加的时候要 new ArrayList(tmp);

3. 别忘了空集也是子集

时间和空间都是取决于结果的数量，也就是O(2^n)。

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

Solutions2：iterator

时间和空间都是取决于结果的数量，也就是O(2^n)。

public class Solution {
    public ArrayList> subsets(int[] S) {
        ArrayList> res = new ArrayList>();
        ArrayList list = new ArrayList();
        res.add(list);
        if(S == null || S.length == 0) {
            return res;
        }
        
        Arrays.sort(S);
        for(int i = 0; i < S.length; i++) {
            int size = res.size();
            for(int j = 0; j < size; j++) {
                list = new ArrayList(res.get(j));
                list.add(S[i]);
                res.add(list);
            }
        }
        
        return res;
    }
}

Reference: http://blog.csdn.net/linhuanmars/article/details/24286377