题解 | #集合的所有子集#

解题思路：从前往后遍历数组，每个元素有选择和不选择 2种状态。
1、选择第i个元素：此时组合结果为=原来的组合 U 原来每一个组合加上元素i 的组合, U表示并集 。
2、不选择第i个元素：此时组合结果不变。
设f(i)表示前i个元素的组合。初始条件 f(0) =[ [] ] ;
递推公式：

f(i) = f(i-1) U foreach(f(i-1)) { f(i-1) U s[i] } i>=1   U表示并集

代码如下：

import java.util.*;

public class Solution {
    ArrayList<Integer> subResult = new ArrayList();
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        // 升序排列
        Arrays.sort(S);
        ArrayList<ArrayList<Integer>> result = new ArrayList();
        ArrayList<Integer> subResult = new ArrayList();
        // 一个都不选择
        result.add(subResult);
        for(int i = 0 ; i< S.length; i++){
            // 选择S[i]时，才会增加状态  原先的SubResult 每个增加一个S[i];
            ArrayList<ArrayList<Integer>> newResult = new ArrayList();
            for(ArrayList<Integer> lastSubResult : result){
                ArrayList<Integer> newSubResult =  new ArrayList();
                newSubResult.addAll(lastSubResult);
                newSubResult.add(S[i]);
                newResult.add(newSubResult);
            }
            result.addAll(newResult);
        }
        return result;
    }
}