78.子集

题目

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

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

示例 1：

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

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

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

思路

实现思路

采用回溯法的方式，通过递归遍历数组，对于每个元素都有选择或不选择两种情况。通过一个全局变量 res 记录当前构建的子集，在递归过程中不断添加元素并回溯，生成所有可能的子集。

关键步骤解析

1. 初始化结果集：创建一个 List<List<Integer>> ans 用于存储所有子集，并首先添加空集。
2. 遍历数组元素：对数组中每个元素作为起点调用 dfs 方法，开始构建包含该元素的子集。
3. 递归构建子集：
   • 将当前元素加入 res 中
   • 将当前 res 的副本加入结果集 ans
   • 对后续元素继续递归调用 dfs
   • 回溯时移除最后加入的元素（res.removeLast()）
4. 终止条件：当 res.size() == nums.length 时，说明已构建了包含所有元素的子集，无需继续递归。

代码

class Solution {
   // 用于收集子集的列表
   private List<Integer> res;
   public List<List<Integer>> subsets(int[] nums) {
      // 答案集合
      List<List<Integer>> ans=new ArrayList<>();
      // 添加空的子集
      ans.add(new ArrayList<>());
      // 通过1，2，3去找对应子集，1，下面有2，3 2下面有3，3下面没有了，这样就能确保不会有重复
      // 因此不需要set来去重，可以节省空间，以及不用集合复制，减少空间复杂度
      for (int i=0;i<nums.length;i++){
         // 创建新的子集集合，避免重复
         res=new ArrayList<>();
         dfs(i,nums,ans);
      }
      // 转化成
      return ans;
   }

   // 深搜
   private void dfs(int i, int[]nums, List<List<Integer>> ans){
      // 如果子集到达nums最大深度就返回
      if(res.size()== nums.length){
         return;
      }
      // 直接添加
      res.add(nums[i]);
      ans.add(new ArrayList<>(res));
      // 遍历1下面的2和3
      for(int j=i+1;j<nums.length;j++){
         dfs(j, nums, ans);
         // 回溯删除最后一个
         res.removeLast();
      }
   }
}

总结

复杂度分析

• 时间复杂度：O(2^n)，其中 n 是数组 nums 的长度。因为每个元素都有选择或不选择两种状态，总共有 2^n 个子集。
• 空间复杂度：O(n)，递归调用栈的最大深度为 n，同时 res 列表最多存储 n 个元素。

核心特点

通过深度优先搜索遍历所有可能的组合情况，利用回溯的思想避免重复计算，能够高效地生成所有子集。算法结构清晰，易于理解和实现。