当前位置：首页 > ai >正文

(每日一道算法题)子集

ai 2025/6/23 18:53:28

78. 子集 - 力扣（LeetCode）

给你一个整数数组 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 中的所有元素 互不相同

方法：DFS回溯法（深度优先搜索）

思路

使用DFS回溯法遍历所有可能的子集组合：

路径记录：使用列表path记录当前已选择的元素

结果集：使用列表ret保存所有找到的子集

递归设计：

每层递归处理一个元素（当前索引n对应的元素）
分别考虑选与不选当前元素的两种情况
递归结束时将路径添加到结果集

关键点解释

终止条件：当处理完所有元素（n == 数组长度），保存当前路径

选择与回溯：

选择当前元素 → 递归处理下一元素 → 回溯移除元素
不选择当前元素 → 直接递归处理下一元素

无副作用递归：使用n+1作为参数传递（而非n++/++n），避免状态污染

代码实现

class Solution {List<List<Integer>> ret; // 结果集List<Integer> path;       // 当前路径（子集）public List<List<Integer>> subsets(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();dfs(nums, 0); // 从索引0开始DFSreturn ret;}private void dfs(int[] nums, int n) {// 终止条件：已处理所有元素if (nums.length == n) {ret.add(new ArrayList<>(path)); // 保存当前子集return;}// 情况1：选择当前元素path.add(nums[n]);dfs(nums, n + 1);  // 处理下一索引path.remove(path.size() - 1); // 回溯// 情况2：不选择当前元素dfs(nums, n + 1);  // 直接处理下一索引}
}

执行流程示例（nums=[1,2]）

递归层	当前元素	选择情况	path状态	操作说明
0	1	选	[1]	递归进入下一层
1	2	选	[1,2]	到达终点→保存[1,2]
1	2	不选	[1]	到达终点→保存[1]
0	1	不选	[]	递归进入下一层
1	2	选	[2]	到达终点→保存[2]
1	2	不选	[]	到达终点→保存空集

复杂度分析

时间复杂度：O(N×2^N)
- 共生成2^N个子集
- 每个子集平均长度O(N)，复制到结果集需O(N)
空间复杂度：O(N)
- 递归调用栈深度最大为N
- 路径列表path长度最多为N

高效DFS解法（循环回溯）

算法思路

这种DFS实现采用循环遍历代替选择分支，核心思想是：

以不同起始点展开搜索：每次递归从pos位置开始遍历数组
路径即子集：每次进入递归就将当前路径作为子集加入结果集
逐步扩展子集：从当前位置开始向后扩展，避免重复元素

代码实现

class Solution {List<List<Integer>> ret; // 结果集List<Integer> path;       // 当前路径（子集）public List<List<Integer>> subsets(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();dfs(nums, 0); // 从索引0开始DFSreturn ret;}private void dfs(int[] nums, int pos) {ret.add(new ArrayList<>(path)); // 保存当前路径作为子集// 从pos开始向后扩展子集for (int i = pos; i < nums.length; i++) {path.add(nums[i]);      // 包含当前元素dfs(nums, i + 1);       // 递归处理后续元素path.remove(path.size() - 1); // 回溯}}
}

执行流程示例（nums=[1,2]）

递归层级	起始位置	当前遍历	操作	path状态	结果集变化
1	0	i=0	添加1，dfs(i+1=1)	[1]	加入空集`[]`
2	1	循环开始	首先保存路径	[1]	加入`[1]`
2	1	i=1	添加2，dfs(i+1=2)	[1,2]	加入`[1,2]`
3	2	-	保存路径后循环不执行	[1,2]	加入`[1,2]`
3	2	-	回溯到上一层	[1]
2	1	循环结束	回溯到上一层	[]
1	0	i=1	添加2，dfs(i+1=2)	[2]	加入`[2]`
2	2	-	保存路径后循环不执行	[2]	加入`[2]`