Hot 100 --- 子集

本文概览：本文以LeetCode题目"子集"为例，讲解选与不选的两种回溯写法——方法一选/不选分支决策树，方法二for循环+start参数

一、题目

子集题目

二、题目分析

题目要求：给定一个没有重复元素的数组，返回所有可能的子集（幂集）

这题考察的是离散数学里的幂集——一个集合所有子集的集合。比如 {1, 2} 的子集有 4 个：

{}        ← 都不选
{1}       ← 只选 1
{2}       ← 只选 2
{1, 2}    ← 都选

n 个元素的子集数 = 2ⁿ，因为每个元素都有"选"或"不选"两种选择

和上一题全排列的区别：全排列关心顺序，{1,2} 和 {2,1} 是不同的排列；子集不关心顺序，{1,2} 和 {2,1} 是同一个子集。所以不需要像全排列那样每次从 0 开始扫描换顺序，只需要按数组顺序往后选，避免产生重复的子集

子集问题有两种常见的回溯写法

思路概览

方法一：选/不选分支（决策树）

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(res, 0, nums, new ArrayList<>());
    return res;
}

private void backtrack(List<List<Integer>> res, int index, int[] nums, List<Integer> path) {
    // 递归出口：处理完所有元素，收集结果
    if (index == nums.length) {
        res.add(new ArrayList<>(path));
        return;
    }
    // 分支1：不选 nums[index]
    backtrack(res, index + 1, nums, path);
    // 分支2：选 nums[index]
    path.add(nums[index]);
    backtrack(res, index + 1, nums, path);
    // 回溯
    path.removeLast();
}

方法二：for 循环 + start

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(res, 0, nums, new ArrayList<>());
    return res;
}

private void backtrack(List<List<Integer>> res, int start, int[] nums, ArrayList<Integer> subset) {
    // 每次进入就收集当前子集
    res.add(new ArrayList<>(subset));
    // 从 start 往后选
    for (int j = start; j < nums.length; j++) {
        subset.add(nums[j]);
        backtrack(res, j + 1, nums, subset);
        // 回溯
        subset.removeLast();
    }
}

思路简要说明

方法一：每个元素两个分支——选或不选，递归 n 层到叶子节点收集结果
方法二：用 for 循环从 start 往后选，每次进入 backtrack 就收集结果，不需要等到选完
两种方法结果相同：都是 2ⁿ 个子集，只是视角不同

方法一：选/不选分支（决策树）

思路

对每个元素做"选"或"不选"两种分支，递归 n 层后到叶子节点收集结果。以 nums = [1, 2] 为例：

           根
          / \
     选1 /   \ 不选1
        /     \
     {1}       {}
     / \       / \
选2 /   \不选2/   \不选2
   /     \   /     \
{1,2}   {1} {}     {2}

4 个叶子节点就是 4 个子集。每往下走一层就是处理一个元素的选/不选

代码

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(res, 0, nums, new ArrayList<>());
    return res;
}

private void backtrack(List<List<Integer>> res, int index, int[] nums, List<Integer> path) {
    // 递归出口：处理完所有元素，收集结果
    if (index == nums.length) {
        res.add(new ArrayList<>(path));
        return;
    }
    // 分支1：不选 nums[index]
    backtrack(res, index + 1, nums, path);
    // 分支2：选 nums[index]
    path.add(nums[index]);
    backtrack(res, index + 1, nums, path);
    // 回溯
    path.removeLast();
}

关键点

index 参数：表示当前处理到第几个元素，每层 index+1，到 nums.length 时收集结果
两个分支：先走"不选"分支（不需要 add），再走"选"分支（add 后递归，回来 removeLast）
只在叶子节点收集：index == nums.length 时才存结果，因为每个元素都做了选择，这才是一个完整的子集

执行过程

以 nums = [1, 2] 为例：

backtrack(index=0, path=[])
├── 不选1 → backtrack(index=1, path=[])
│   ├── 不选2 → backtrack(index=2, path=[])
│   │   └── 收集 []                    ← {}
│   └── 选2 → backtrack(index=2, path=[2])
│       └── 收集 [2]                   ← {2}
├── 选1 → backtrack(index=1, path=[1])
│   ├── 不选2 → backtrack(index=2, path=[1])
│   │   └── 收集 [1]                   ← {1}
│   └── 选2 → backtrack(index=2, path=[1,2])
│       └── 收集 [1,2]                 ← {1,2}

结果：[[], [2], [1], [1,2]]，共 4 个 = 2²

方法二：for 循环 + start

思路

不显式区分"选/不选"两个分支，而是用 for 循环从 start 往后遍历，每次进入 backtrack 就收集结果，然后选一个元素往下走

和方法一的区别：方法一每个元素必须选或不选，递归 n 层到叶子才收集；方法二每次进入就收集，for 循环从 start 往后选，天然避免了重复

代码

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(res, 0, nums, new ArrayList<>());
    return res;
}

private void backtrack(List<List<Integer>> res, int start, int[] nums, ArrayList<Integer> subset) {
    // 每次进入就收集当前子集
    res.add(new ArrayList<>(subset));
    // 从 start 往后选
    for (int j = start; j < nums.length; j++) {
        subset.add(nums[j]);
        backtrack(res, j + 1, nums, subset);
        // 回溯
        subset.removeLast();
    }
}

关键点

每次进入 backtrack 就收集：子集不需要选满 n 个元素，空集是子集，选了 1 个也是子集，选了 2 个也是子集。所以第一件事就是 res.add(new ArrayList<>(subset))
start 控制只往后选：for 循环从 start 开始而不是 0，保证只往后选不回头，避免 {1,2} 和 {2,1} 重复
回溯 = 选完后撤销换下一个：选了 nums[j] 往下递归，回来后 removeLast，for 循环 j++ 相当于"这个不选了，选下一个"

选就是 add，不选就是 removeLast 后让 for 循环选下一个。进入 backtrack 先存结果就是"到这为止不选后面的了"，for 循环往下选就是"选这个"

为什么每次进入就存结果？

方法一在每个元素都做了选/不选后，到叶子节点才收集。方法二不一样——任何一种选择组合都是子集，不管选了几个元素：

path = []     → 空集，是子集
path = [1]    → 选了 1，是子集
path = [1,2]  → 选了 1 和 2，是子集
path = [1,2,3]→ 全选，是子集

所以每次进入 backtrack 就存，不需要等到选完

start 参数的作用

全排列每次从 i=0 开始扫描，因为要换顺序产生不同的排列。但子集不关心顺序，{1,2} 和 {2,1} 是同一个子集，所以只往后选就行

start = 0: 可选 1, 2, 3
  选了 1
    start = 1: 可选 2, 3（不能回头选 1，否则 {1,2,1} 没意义）
      选了 2
        start = 2: 可选 3

backtrack(res, j + 1, nums, subset) 中 j+1 就是把 start 移到下一个位置，保证后面的选择只从 j+1 往后取

执行过程

以 nums = [1, 2, 3] 为例：

backtrack(start=0, path=[])
├── add []                              ← ① 收集空集
├── i=0: add 1 → backtrack(start=1, path=[1])
│   ├── add [1]                         ← ② 收集 {1}
│   ├── i=1: add 2 → backtrack(start=2, path=[1,2])
│   │   ├── add [1,2]                   ← ③ 收集 {1,2}
│   │   ├── i=2: add 3 → backtrack(start=3, path=[1,2,3])
│   │   │   ├── add [1,2,3]             ← ④ 收集 {1,2,3}
│   │   │   └── (for 不执行)
│   │   └── remove 3
│   ├── i=2: add 3 → backtrack(start=3, path=[1,3])
│   │   ├── add [1,3]                   ← ⑤ 收集 {1,3}
│   │   └── (for 不执行)
│   └── remove 3
├── i=1: add 2 → backtrack(start=2, path=[2])
│   ├── add [2]                         ← ⑥ 收集 {2}
│   ├── i=2: add 3 → backtrack(start=3, path=[2,3])
│   │   ├── add [2,3]                   ← ⑦ 收集 {2,3}
│   │   └── (for 不执行)
│   └── remove 3
├── i=2: add 3 → backtrack(start=3, path=[3])
│   ├── add [3]                         ← ⑧ 收集 {3}
│   └── (for 不执行)
└── remove 3

结果：[[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]，共 8 个 = 2³

两种方法对比

	方法一：选/不选分支	方法二：for 循环 + start
分支方式	每个元素两个分支：选 / 不选	for 循环从 start 往后选
收集时机	只在叶子节点收集	每次进入 backtrack 就收集
递归参数	index（当前处理第几个）	start（从哪开始选）
代码结构	两路递归 + index+1	for 循环 + start 参数
结果	2ⁿ 个子集	2ⁿ 个子集

两种方法本质相同，只是视角不同。方法一直观体现"选/不选"的思想，方法二代码更简洁，后续的组合、切割问题也会用方法二的模板

复杂度分析

时间复杂度：O(n × 2ⁿ)，共 2ⁿ 个子集，每个子集需要 O(n) 时间复制到结果
空间复杂度：O(n)，递归深度最大为 n，subset 最多存 n 个元素