LeetCode78子集

描述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例

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

思路

子集问题是从 n 个元素的集合中找出满足某种性质的子集。

对于集合中的每个元素有两种状态——在集合中和不在集合中，因此可以使用暴力搜索——回溯法进行求解，穷举每一个元素的状态。

采用回溯法一般需要找出问题的解空间树，然后对解空间树采用深度搜索策略对答案进行搜索。

子集问题的解空间树叫做子集树，因此子集树是问题【在给定n个元素的集合中找出满足某种性质的子集】的响应解空间，典型的01背包问题就可以采用回溯法进行求解。

该问题的解空间树如下所示：

在解空间树中，一个节点代表一个状态，每一层代表你在第几层函数中（可以看做是你在第几层递归中）。

比如下面这张图，这个状态就代表第k层你对第k个元素做的选择。由于每个元素只存在两种状态，所以就对这两种状态进行列举——即选和不选。当所有元素都列举完的时候，就得到了一个子集。然后所有子集加入结果集中。

img

该问题还有一种形式的解空间树，就是采用类似排列树的方式去得到子集。

以下是另一种解空间树（决策的遍历）的形态。

以[1,2,3]为例，第一个位置有三种选择（选择列表），分别是【1】【2】【3】。第一个位置放了【1】后，第二个位置就只能放置【2】或者【3】，所以下一层的选择列表是【2】【3】。下一个位置只能选择当前位置后面的元素。所以此时第k层的状态就是第k个位置上可以放置的元素。

img

其实不同的解空间树代表着不同的决策方式，所以我们写算法的重点就在决策方式，深度搜索和回溯只是一种辅助手法。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> subres = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        res.add(new ArrayList<>(subres));
        dfs2(nums, 0);
        return res;
    }
    
    private void dfs1(int[] nums, int cur){
        if(cur == nums.length){
            // 死结点即为问题解，加入结果集
            ans.add(new ArrayList<>(subres));
            return;
        }
        // 选择当前元素
        subres.add(nums[cur]);
        dfs1(nums, cur+1);
        // 不选当前元素
        subres.remove(subres.size()-1);
        dfs1(nums, cur);
    }

    private void dfs2(int[] nums, int pos){
        if(nums.length == pos) {
            return;
        }
        for(int i = pos; i < nums.length; ++i){ 
            // i = pos，从当前位置开始对值进行选择
            subres.add(nums[i]);// 将选择的值加入到数组中
            res.add(new ArrayList<>(subres));// 将该子集加入结果集中
            dfs2(nums, i+1);
            subres.remove(subres.size()-1); // 撤销选择的结果，回到上一层状态中
        }

    }
}