代码随想录算法训练营第二十七天| 78.子集| 90.子集II

78.子集|

// 将box状态添加到答案中
void append(List<Integer> box, List<List<Integer>> answer) {
    answer.add(new ArrayList<>());
    for (Integer x : box) {
        answer.get(answer.size() - 1).add(x);
    }
}

void backTrace(int[] A,
               int start, /* 第i个人 */
               List<Integer> box,
        /* 箱子的状态 */
               List<List<Integer>> all) {
    // 总的宝石数
    final int N = A == null ? 0 : A.length;
    // 把当前箱子的状态放到结果中，因为要的是所有的子集
    append(box, all);
    // 如果我是最后一个人，并且没有东西给我选了/ 那么原样返回箱子
    if (start >= N) {
        return;
    }
    // 我还是有宝石可以选择的。
    for (int j = start; j < N; j++) {
        box.add(A[j]);
        // /注意这里结论1的使用，所以这里要写[i + 1,end)
        backTrace(A, j + 1, box, all);
        box.remove(box.size() - 1);
    }
}

public List<List<Integer>> subsets(int[] A) {
    final int N = A == null ? 0 : A.length;
    List<Integer> box = new ArrayList<>(0);
    List<List<Integer>> ans = new ArrayList<>(0);
    backTrace(A, 0, box, ans);
    return ans;
}

?90.子集II