78. 子集 78. Subsets

[Shellbye]

题目描述

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 说明：解集不能包含重复的子集。 示例:

输入: nums = [1,2,3] 输出:

[
 [3],
 [1],
 [2],
 [1,2,3],
 [1,3],
 [2,3],
 [1,2],
 []
]

第一种思路

我觉得比较常规的一种思路（也是我的第一反应），就是先列出所有长度为 1 的子集，然后在长度为 1 的子集的基础上，分别添加新元素，构成长度为 2 的子集，然后是长度为 3 的子集...直到长度为 nums.length 的子集，即全体元素的一个最大子集。 比如如下长度为 1 的子集

[
 [1]
 [2]
 [3]
 [4]
 [5]
]

在分别给其中每个子集添加元素，构成长度为 2 的子集如下：

[
 [1,2]
 [1,3]
 [1,4]
 [1,5]

 [2,3]
 [2,4]
 [2,5]

 [3,4]
 [3,5]

 [4,5]
]

在分别给其中每个子集添加元素，构成长度为 3 的子集如下：

[
 [1,2,3]
 [1,2,4]
 [1,2,5]

 [1,3,4]
 [1,3,5]

 [1,4,5]

 [2,3,4]
 [2,3,5]
...
]

这种思路想起来比较容易，但是用代码实现是比较麻烦的，我尝试了好久，都没有正确的实现出来。

另一个思路

看了看别人的一些思路，发现以下这种是比较容易理解的一个版本。

    public List<List<Integer>> subsets(int[] nums) {
        // 逐个枚举，空集的幂集只有空集，每增加一个元素，让之前幂集中的每个集合，追加这个元素，就是新增的子集
        List<List<Integer>> ret = new ArrayList<>();
        ret.add(new ArrayList<>());
        for (int i = 0; i < nums.length; i++) {
            int size = ret.size();
            for (int j = 0; j < size; j++) {
                List<Integer> pre = new ArrayList<>(ret.get(j)); // addAll 的构造写法
                pre.add(nums[i]);
                ret.add(pre);
            }
        }
        return ret;
    }

这个版本的思路就是从空集开始，依次从 nums 中取出一个数字，并给已经有的子集分别添加该数字，构成新的子集并，直到处理完全部 nums 中的数字。这个思路相比上一个思路，实现起来比较容易，因为每一个新出现的数字，都是直接往所有已经存在的子集中直接添加，不需要考虑重复问题。