LeetCode 78 子集

LeetCode 78

首先数组内的元素是不会重复的，但返回子集不能有重复

关于题解，有一个非常巧妙的解法，追加子集，将思路进行画图讲解

1.空集合是所有集合的子集

2.每次将i追加到已有子数组的集合中

3.当指针移动到最后一个元素即遍历完毕

代码部分

public static List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    result.add(new ArrayList<>());
    //子集中必然包含一个空数组
    for (int num : nums) {

        List<List<Integer>> sub = new ArrayList<List<Integer>>();
        for (List<Integer> integers : result) {
            List<Integer> temp = new ArrayList<>(integers);
            temp.add(num);
            sub.add(temp);
        }
        for (List<Integer> integers : sub) {
            result.add(integers);
        }
    }
    return result;
}

public static void main(String[] args) {

    int[] nums = {
        2,6,9,8,7
    };
    System.out.println(subsets(nums));
}

[[], [2], [6], [2, 6], [9], [2, 9], [6, 9], [2, 6, 9], [8], [2, 8], [6, 8], [2, 6, 8], [9, 8], [2, 9, 8], [6, 9, 8], [2, 6, 9, 8], [7], [2, 7], [6, 7], [2, 6, 7], [9, 7], [2, 9, 7], [6, 9, 7], [2, 6, 9, 7], [8, 7], [2, 8, 7], [6, 8, 7], [2, 6, 8, 7], [9, 8, 7], [2, 9, 8, 7], [6, 9, 8, 7], [2, 6, 9, 8, 7]]