0078.子集

题目链接

78. 子集 - 力扣（LeetCode）

题目描述

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

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

题目示例

示例 1 :

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

示例 2 :

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

解题思路

题目要求生成给定数组的所有可能子集（包括空集）。通过回溯算法，在每一步选择是否包含当前元素，递归生成所有可能的组合。

题解代码

classSolution{privatefinalList<List<Integer>>ans=newArrayList<>();// 存储所有子集的结果列表privatefinalList<Integer>path=newArrayList<>();// 当前递归路径（当前子集）privateint[]nums;// 输入数组publicList<List<Integer>>subsets(int[]nums){this.nums=nums;// 初始化输入数组dfs(0);// 从第0个元素开始递归returnans;}// 回溯函数：处理第i个元素的选择与不选privatevoiddfs(inti){if(i==nums.length){// 所有元素处理完毕ans.add(newArrayList<>(path));// 将当前路径拷贝到结果列表return;}// 不选当前元素nums[i]dfs(i+1);// 直接递归处理下一个元素// 选当前元素nums[i]path.add(nums[i]);// 将当前元素加入路径dfs(i+1);// 递归处理下一个元素path.remove(path.size()-1);// 回溯：移除最后添加的元素（恢复现场）}}

复杂度分析

• 时间复杂度：O(n × 2ⁿ)
  • 每个元素有选/不选两种可能，总共有2ⁿ个子集。
  • 每个子集被复制到结果列表需要O(n)时间，总时间复杂度为O(n × 2ⁿ)。
• 空间复杂度：O(n × 2ⁿ)
  • 结果列表存储2ⁿ个子集，每个子集平均长度为n/2。
  • 递归调用栈深度为O(n)。