78. 子集

---

题目

描述： 给你一个整数数组 nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。 解集不能包含重复的子集。你可以按任意顺序返回解集。

示例： 示例 1:

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

示例 2:

输入: nums = [0]
输出: [[],[0]]

---

解题思路

核心方法

回溯法：

1. 路径选择：维护一个临时列表 temp，存储当前已选择的元素。
2. 递归终止条件：每次递归开始时，将当前临时列表加入结果列表（因为子集可以是空集或任意长度的元素组合）。
3. 回溯过程：从当前深度 depth 开始遍历数组，将元素加入临时列表，递归进入下一层（深度+1）；递归返回后，将该元素从临时列表中移除，继续尝试其他选择。
4. 避免重复：通过控制遍历的起始位置（从 depth 开始），确保每个元素只被选择一次，从而避免生成重复的子集。

---

代码实现

回溯法（Java）

import java.util.*;

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    
    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums, 0);
        return ans;
    }
    
    public void dfs(int[] nums, int depth) {
        ans.add(new ArrayList<>(temp));
        for (int i = depth; i < nums.length; i++) {
            temp.add(nums[i]);
            dfs(nums, i + 1);
            temp.remove(temp.size() - 1);
        }
    }
}

---

复杂度分析

• 时间复杂度：O(n * 2^n)，其中 n 是数组的长度。每个元素有选或不选两种状态，共有 2^n 个子集，每个子集需要 O(n) 的时间复制到结果列表中。
• 空间复杂度：O(n)，递归栈的深度为 n，临时列表的空间也为 n。

---

总结

1. 回溯法是解决子集问题的经典方法，通过控制遍历的起始位置，能够高效生成所有可能的子集。
2. 每次递归开始时将当前路径加入结果列表，确保了空集和所有中间子集都被包含。
3. 该方法适用于不含重复元素的数组，若数组包含重复元素，需要额外的去重逻辑。

---