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

import java.util.*;

public class Solution {

    ArrayList<ArrayList<Integer>> result = new  ArrayList<ArrayList<Integer>>();

    public ArrayList<ArrayList<Integer>> subsets(int[] S) {

        ArrayList<Integer> list = new ArrayList<Integer>();

        Arrays.sort(S);

        for (int i = 0; i <= S.length; i++) {
            backTracing(i, 0, S, list);
        }
        return result;
    }

    // 如:1234 结果应该是
    // 1:k= 0表示增加: [] 
    // 2:k= 1 start=0表示增加: [1] [2] [3] [4]
    // 3:k= 2表示先增加[1],然后在[1]的基础上分别增加[2],[3],[4],结果: [1,2] [1,3] [1,4] 
    // 4:k= 3表示先增加[1],然后在上一步的结果再针对 [1,2] [1,3] [1,4] 中的[1,2]添加3,4 [1,2,3],[1,2,4], 再给[1,3]追加4 [1,3,4]
    // 5:k= 4表示增加: 针对[1,2,3]追加4,[1,2,3,4]
    // 可以看出 每次都是在原有的集合的基础上 增加后面的每一个元素 组成一个新的子集合 如果当前元素后面没有元素了,那么不会被添加到result里面,会被list.remove回溯删除掉
    // k就表示 为list追加几个元素
    public void backTracing (int k, int start, int[] arr, ArrayList<Integer> list) {

        if (k == 0) {
            result.add(new ArrayList(list));
            return;
        }

        for (int j = start; j < arr.length; j++) {
            list.add(arr[j]);
            backTracing(k - 1, j + 1, arr, list);
            list.remove(list.size() - 1);
        }
    }
}