企业官网建设流程全解析

一句话说明核心方法

本题用回溯(DFS)枚举每个元素"选 / 不选"两种决策,递归树上的每个节点都收集一份答案,正好得到 2ⁿ 个子集,完整覆盖整个幂集。

思路推导

题意转化:返回 nums 所有可能的子集,等价于"对每个下标 i 决定要不要把 nums[i] 放进当前子集",每个下标 2 种决策 → 共 2ⁿ 种组合。

关键观察:这正好是"枚举一棵深度为 n 的二叉决策树",每条根→叶的路径对应一种子集的所有元素选/不选组合。

算法选择:回溯天然适合遍历决策树,且能在递归过程中"边走边收",不需要单独枚举 0/1 串。

与排列的区别:排列要求顺序敏感,递归参数是i+1(每层从头遍历剩余元素);子集要去重 + 升序,递归参数是start,且每个节点都要 add(排列只在叶子收)。

回溯树示意(nums = [1,2,3])

[] ← 入口,也是合法子集 ┌───────────┴───────────┐ 不选 1 选 1 │ │ [] [1] ┌───┴───┐ ┌───┴───┐ 不选 2 选 2 不选 2 选 2 │ │ │ │ [] [2] [1] [1,2] ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ 不选3 选3 不选3 选3 不选3 选3 不选3 选3 │ │ │ │ │ │ │ │ [] [3] [2] [2,3] [1][1,3][1,2][1,2,3] ↓ 全 8 个子集,正好 2^3

Java 完整代码

class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> res = new ArrayList<>(); List<Integer> path = new ArrayList<>(); back(nums, 0, path, res); return res; } private void back(int[] nums, int start, List<Integer> path, List<List<Integer>> res) { //关键:每个递归节点都收集一份当前 path,对应决策树的"每个节点" res.add(new ArrayList<>(path)); // 从 start 开始,避免重复选同一位置,也保证子集元素下标递增 for (int i = start; i < nums.length; i++) { // 1. 选 nums[i] path.add(nums[i]); // 2. 递归到下一层,起始位置 i+1 表示 nums[i] 不能再用 back(nums, i + 1, path, res); // 3. 撤销选择(回溯) path.remove(path.size() - 1); } } }

关键代码逐行解释

• res.add(new ArrayList<>(path))放在递归入口、for 循环之前——每个节点都收集。这是子集和排列、组合最大的区别:排列只在叶子节点收,子集每层都收。必须new ArrayList<>(path)拷贝一份,因为 path 在后续递归中会被改动,直接add(path)会让所有子集指向同一个对象,最后全部错。
• for (int i = start; ...)的start参数至关重要——保证子集内元素下标严格递增,天然去重。例如生成[2]后,下一层只能从 i=2 开始,不能回头再选 nums[0]=1,所以也不会出现[2,1]这种重复。
• back(nums, i + 1, ...)而不是back(nums, start + 1, ...)——每个分支独立推进。如果写成start+1,选了 nums[start] 之后下一层就只能从 start+1 开始,会丢失[1,3]这种"跳过中间元素"的子集。
• path.remove(path.size() - 1)撤销上一步加入,保证回到父节点时 path 状态正确。这是回溯"对称性"的体现:加入和撤销必须严格配对,否则递归结束后 path 里会残留脏数据。

时间、空间复杂度

• 时间复杂度:O(n · 2ⁿ)
  • 决策树节点数 2ⁿ(每个下标选/不选两种状态),每个节点都要做一次new ArrayList<>(path)拷贝,拷贝长度 ≤ n,总代价 O(n · 2ⁿ)。
• 空间复杂度:O(n)(不计输出)
  • 递归栈最深 n 层,path 长度也 ≤ n。输出结果本身占 O(n · 2ⁿ),题目要求返回,无法避免。

易错点

• 引用 vs 拷贝:res.add(path)是错的,所有子集都会指向同一个 path 对象,后续被改了就全错。必须new ArrayList<>(path)。
• 忘了在入口 add:把res.add(...)放到 for 循环里、或者挪到叶子位置,只会得到叶子节点的结果,漏掉所有"中间子集"(空集、单元素、长度< n 的子集全丢)。
• 递归参数错:写成back(nums, start + 1, ...)会丢子集;写成back(nums,0, ...)会导致重复子集(同一组合被多次生成)。
• 没考虑空集:空集[]也是合法子集。本题靠"入口处无条件 add"自动覆盖,不需要手动加,但要意识到它是递归入口那次调用收集到的。

可复用模板

回溯的"子集 / 组合 / 排列"系列都可以套下面这个框架,主要改两处:add条件和参数推进方式。

java

class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> res = new ArrayList<>(); List<Integer> path = new ArrayList<>(); backtrack(nums, 0, path, res); return res; } // 模板:回溯 = 收集 + 循环选择 + 加入/递归/撤销 private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) { res.add(new ArrayList<>(path)); // ★ 子集:每层都收 for (int i = start; i < nums.length; i++) { path.add(nums[i]); // 1. 选 backtrack(nums, i + 1, path, res); // 2. 递归(start 推进 +1) path.remove(path.size() - 1); // 3. 撤销 } } }

变体提示:

• 改成"组合"(LeetCode 77)→ 在add前判断path.size() == k,且只在叶子收。
• 改成"排列"(LeetCode 46)→ 去掉start参数,加boolean[] used,进入时检查!used[i]。
• 改成"子集去重"(LeetCode 90)→ 先Arrays.sort(nums),在 for 里加if (i > start && nums[i] == nums[i-1]) continue。

相似题及区别

• LeetCode 77 组合:本题的"取 k 个元素"版本。只收集path.size() == k的叶子节点;本题每层都收集。
• LeetCode 46 全排列:顺序敏感,所以没有start参数,而是用boolean[] used标记已选元素;且只在叶子收。本题用start控制升序去重。
• LeetCode 90 子集 II:nums 含重复元素,需要先排序 + 在 for 循环里加if (i > start && nums[i] == nums[i-1]) continue跳过同层重复。本题 nums 元素互不相同,无需这步。
• LeetCode 491 递增子序列:子集但要求元素递增,且不能排序(顺序由原数组决定),要在每层用HashSet去重。和本题"靠下标递增去重"的思路完全不同。