题解 | #集合的所有子集(一)，O(n*n!)#

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        Arrays.sort(S) ;
        ArrayList<ArrayList<Integer>> res = new ArrayList<>() ;
        res.add(new ArrayList<Integer>()) ;
        for(int len = 1 ; len <= S.length ; len ++) {//长度，求出每一种按长度的所有情况
            int resSize = res.size() ;
            for(int k = 0 ; k < resSize ; k ++) {//要求长度n的所有情况，先遍历拿到长度n-1的所有情况
                ArrayList<Integer> list = res.get(k) ;
                if(list.size() == len - 1) {
                    int start = list.size() == 0 ? Integer.MIN_VALUE : list.get(list.size() - 1) ;
                    for(int i = 0 ; i < S.length ; i ++) {//在n-1的每一种情况后面，添加一位更大的数
                        if(S[i] <= start) continue ;
                        ArrayList<Integer> new_list = new ArrayList(list) ;
                        new_list.add(S[i]) ;
                        res.add(new_list) ;
                    }
                }
            }
        }
        return res ;
    }
}