78.子集

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

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

示例 1：

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

示例 2：

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

Solution

输入视角：

对于一个数，要做的只有选or不选

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
class Solution {
    private final List<List<Integer>> ans = new ArrayList<>();  // 定义一个列表来存储所有子集
    private final List<Integer> path = new ArrayList<>();       // 用来存储当前递归路径的子集
    private int[] nums;                                         // 用于存储输入的数组

    public List<List<Integer>> subsets(int[] nums) {
        this.nums = nums;  // 将传入的数组引用保存到实例变量nums中
        dfs(0);            // 从数组的第一个元素开始深度优先搜索（DFS）
        return ans;        // 返回包含所有子集的列表
    }

    private void dfs(int i) {
         // 如果索引i等于数组长度，说明已遍历完所有元素
        if (i == nums.length) {
            // 将当前路径（子集）复制并添加到答案列表中
            ans.add(new ArrayList<>(path));     
            return;
        }
        // 不选择当前元素 nums[i]
        dfs(i + 1);
        // 选择当前元素 nums[i]
        path.add(nums[i]);   // 将当前元素添加到路径中
        dfs(i + 1);          // 继续递归下一个元素
        path.remove(path.size() - 1);  // 回溯，移除路径中最后一个元素，恢复到选择前的状态
    }
}

答案视角：

每次都要选一个数

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
class Solution {
    // ans 用来存储所有的子集
    private final List<List<Integer>> ans = new ArrayList<>();
    // path 用来记录当前递归路径上选择的元素，即当前正在构建的子集
    private final List<Integer> path = new ArrayList<>();
    // nums 存储输入的数组
    private int[] nums;

    // 公共方法，输入是一个整数数组，输出是这个数组的所有子集
    public List<List<Integer>> subsets(int[] nums) {
        this.nums = nums;  // 将输入的数组存储到类的成员变量nums中，供整个类使用
        dfs(0);            // 从数组的第一个元素开始深度优先搜索
        return ans;        // 返回包含所有子集的列表
    }

    // 使用深度优先搜索（DFS）生成所有子集
    private void dfs(int i) {
        ans.add(new ArrayList<>(path)); // 将当前路径（即当前构建的子集）复制并添加到结果列表中
        if (i == nums.length) return;   // 如果索引i等于数组长度，说明已经考虑完所有元素，返回结束递归
        for (int j = i; j < nums.length; ++j) { // 从索引i开始，枚举可能选择的元素
            path.add(nums[j]);                  // 选择元素nums[j]，加入到当前路径中
            dfs(j + 1);                         // 递归调用dfs，考虑下一个元素
            path.remove(path.size() - 1);       // 撤销选择，即从path中移除最后一个元素，恢复到选择前的状态
        }
    }
}