知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 03 - 子集 ## 题目(LeetCode 78) 给定一个不含重复元素的整数数组 nums,返回其所有可能的子集。 ``` 输入:[1, 2, 3] 输出:[[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]] ``` ## 大白话理解 对每个元素,你只有两个选择:选它 或 不选它。 ``` 元素 1:选 or 不选 元素 2:选 or 不选 元素 3:选 or 不选 2 × 2 × 2 = 8 种组合,正好是 2^3 = 8 个子集 ``` 换个角度看:子集就是"从数组中挑任意个元素的所有组合"。和排列不同,子集没有顺序,`[1,2]` 和 `[2,1]` 是同一个子集。 ## 决策树 ``` startIndex=0 [] / | \ startIndex=1 [1] [2] [3] / \ | startIndex=2 [1,2] [1,3] [2,3] | [1,2,3] 每个节点都是一个合法的子集(不只是叶子节点) ``` ## 代码 ```java class Solution { private List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> subsets(int[] nums) { backtrack(nums, 0, new ArrayList<>()); return result; } private void backtrack(int[] nums, int startIndex, List<Integer> path) { // 每个节点都是一个子集,直接收集 result.add(new ArrayList<>(path)); for (int i = startIndex; i < nums.length; i++) { path.add(nums[i]); // 选择 nums[i] backtrack(nums, i + 1, path); // 从 i+1 开始,避免重复 path.remove(path.size() - 1); // 撤销选择 } } } ``` ### 和排列的关键区别 ``` 排列:for (int i = 0; ...) 每次从头开始,用 used 标记 子集:for (int i = startIndex; ...) 只往后选,天然避免重复 排列 [1,2] 和 [2,1] 不同 → 需要从头选 子集 {1,2} 和 {2,1} 相同 → 只往后选 ``` ### 为什么没有终止条件? 因为每个节点都要收集结果,不需要等到叶子节点。当 `startIndex == nums.length` 时,for 循环自然不会执行,递归自动结束。 ## 变体:子集 II(LeetCode 90)— 有重复元素 ``` 输入:[1, 2, 2] 输出:[[], [1], [2], [1,2], [2,2], [1,2,2]] 不能有 [2] 出现两次 ``` ```java public List<List<Integer>> subsetsWithDup(int[] nums) { Arrays.sort(nums); // 排序,让相同元素相邻 backtrack(nums, 0, new ArrayList<>()); return result; } private void backtrack(int[] nums, int startIndex, List<Integer> path) { result.add(new ArrayList<>(path)); for (int i = startIndex; i < nums.length; i++) { // 同一层中跳过重复元素 if (i > startIndex && nums[i] == nums[i - 1]) continue; path.add(nums[i]); backtrack(nums, i + 1, path); path.remove(path.size() - 1); } } ``` 去重的关键:`i > startIndex`(不是 `i > 0`),确保是同一层的重复才跳过。 ``` nums = [1, 2a, 2b] 同一层选 2a 后,不再选 2b(重复) 但不同层可以:[2a, 2b] 是合法的(选了第一个 2,还可以选第二个 2) i > startIndex 保证的是:在当前层的循环中,跳过和前一个相同的元素 ``` ## 复杂度 - 时间:O(2^n × n),共 2^n 个子集,每个子集拷贝 O(n) - 空间:O(n) ## 一句话总结 子集 = 每个节点都收集 + startIndex 往后选。有重复就排序 + 同层跳过。 --- 上一篇:[02 - 全排列](./02-permutations.md) | 下一篇:[04 - 组合总和](./04-combination-sum.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入