回溯例题：子集型

看一下灵神的思路
方法一：选或不选（输入的视角）
对于输入的 nums，考虑每个 nums[i] 是选还是不选，由此组合出 2的n个不同的子集。

dfs 中的 i 表示当前考虑到 nums[i] 选或不选。

答疑
问：为什么要恢复现场？

答：我们来做个实验。去掉代码中的恢复现场那行代码，然后测试 nums=[1,2] 这个数据。你会发现答案居然包含 [2,1,2]，这是为什么呢？

看视频中的图。如果不恢复现场，当我们从 [2] 递归返回后，path 中还残留有 2，对于后面的递归来说，这个 2 是多余的。继续递归「选 1」的右子树时，会把 1 加到 path 中，导致 path=[2,1]；继续递归到「选 2」的右子树时，path=[2,1,2]，显然这是错的。

class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
ans = []
path = []

    # 选或不选：讨论 nums[i] 是否加入 path
    def dfs(i: int) -> None:
        if i == n:  # 子集构造完毕
            ans.append(path.copy())  # 复制 path，也可以写 path[:]
            return

        # 不选 nums[i]
        dfs(i + 1)  # 考虑下一个数 nums[i+1] 选或不选

        # 选 nums[i]
        path.append(nums[i])
        dfs(i + 1)  # 考虑下一个数 nums[i+1] 选或不选
        path.pop()  # 恢复现场，撤销 path.append(nums[i])

    dfs(0)
    return ans

复杂度分析
时间复杂度：O(n乘以2的n)，其中 n 为 nums 的长度。有 2的n
个子集，所以搜索树有 2的n
个叶子，每个叶子复制 path 需要 O(n) 的时间，一共需要 O(n乘以2的n) 时间。
空间复杂度：O(n)。返回值的空间不计。
方法二：枚举选哪个（答案的视角）
枚举子集（答案）的第一个数选谁，第二个数选谁，第三个数选谁，依此类推。

dfs 中的 i 表示现在要枚举选 nums[i] 到 nums[n−1] 中的一个数，添加到 path 末尾。

如果选 nums[j] 添加到 path 末尾，那么下一个要添加到 path 末尾的数，就要在 nums[j+1] 到 nums[n−1] 中枚举了。

注意：不需要在回溯中判断 i=n 的边界情况，因为此时不会进入循环，if i == n: return 这句话写不写都一样。

class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
ans = []
path = []

    # 枚举选哪个：在下标 i 到 n-1 中选一个数，加到 path 末尾
    def dfs(i: int) -> None:
        ans.append(path.copy())  # 不选，把当前子集加入答案
        for j in range(i, n):  # 选，枚举选择的数字
            path.append(nums[j])
            dfs(j + 1)  # 选 nums[j] 意味着 i 到 j-1 都跳过不选，下一个数从 j+1 开始选
            path.pop()  # 恢复现场

    dfs(0)
    return ans

复杂度分析
时间复杂度：O(n乘以2的n)，其中 n 为 nums 的长度。答案的长度为子集的个数，即2的n
，同时每次递归都把一个数组放入答案，因此会递归 2的n
次，再算上加入答案时复制 path 需要 O(n) 的时间，所以时间复杂度为 O(n乘以2的n)。
空间复杂度：O(n)。返回值的空间不计。
方法三：二进制枚举
根据 从集合论到位运算，常见位运算技巧分类总结 中的「枚举子集」的技巧，可以只用简单的循环枚举所有子集。

class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
ans = []
for i in range(1 << len(nums)): # 枚举全集 U 的所有子集 i
subset = [x for j, x in enumerate(nums) if i >> j & 1]
ans.append(subset)
return ans
复杂度分析
时间复杂度：O(n乘以2的n)，其中 n 为 nums 的长度。
空间复杂度：O(1)。返回值的空间不计。

子集型回溯笔记

1. 前提条件

子集型问题问的是：

给你一组数，每个数可以选，也可以不选。
求所有可能的集合。

典型题：

78. 子集
79. 子集 II
80. 分割回文串
81. 电话号码的字母组合

最基础例子：

nums = [1,2,3]

答案：

[]
[1]
[2]
[3]
[1,2]
[1,3]
[2,3]
[1,2,3]
2. 核心概念

子集型回溯本质是：

每个元素都有两个选择：

选
不选

比如 [1,2,3]：

1：选 / 不选
2：选 / 不选
3：选 / 不选

所以总共有：

2^n 个子集
3. 回溯三件套

子集型回溯一定会有：

path：当前已经选了哪些数

start / index：当前从哪里开始选

ans：保存所有答案

其中：

path 是临时路径
ans 是最终答案
4. 写法一：选 / 不选

这是最接近“每个数选不选”的写法。

核心模板
void dfs(int index)
{
if(index == numsSize)
{
保存 path;
return;
}

// 不选 nums[index]
dfs(index + 1);

// 选 nums[index]
path[pathSize++] = nums[index];
dfs(index + 1);
pathSize--;

}
怎么理解

比如：

nums = [1,2]

递归树：

             []
          /      \
      不选1       选1
       []         [1]
     /   \       /   \
 不选2  选2   不选2  选2
   []   [2]    [1]  [1,2]

最后得到：

[]
[2]
[1]
[1,2]

顺序不重要，内容对就行。

为什么要 pathSize--
path[pathSize++] = nums[index];
dfs(index + 1);
pathSize--;

意思是：

先把 nums[index] 放进 path
递归搜索后面的选择
回来以后撤销刚刚这个选择

如果不撤销，后面分支会带着错误的 path。

5. 写法二：枚举下一个选谁

这是灵神常用写法，也更适合后面组合题。

核心模板
void dfs(int start)
{
保存 path;

for(int i = start; i < numsSize; i++)
{
    path[pathSize++] = nums[i];

    dfs(i + 1);

    pathSize--;
}

}

这版的意思是：

当前 path 本身就是一个子集，先保存。

然后从 start 开始，枚举下一个要加入 path 的数。
用 [1,2,3] 走一遍

开始：

path = []
start = 0

先保存：

[]

然后循环：

选 1：

path = [1]

保存：

[1]

继续从 2 开始选：

[1,2]
[1,2,3]
[1,3]

回到最外层，选 2：

[2]
[2,3]

再选 3：

[3]

最终：

[]
[1]
[1,2]
[1,2,3]
[1,3]
[2]
[2,3]
[3]
6. 为什么递归是 dfs(i + 1)

因为子集里：

每个数只能用一次
并且不能回头选

例如已经选了 2，后面只能考虑 3，不能再回头选 1。

所以：

dfs(i + 1);

表示：

下一层只能从 i 后面的元素开始选

这样可以避免重复：

[1,2]
[2,1]
7. 子集型核心代码 C 版

先写一个用于理解的打印版。

#include <stdio.h>

#define MAXN 20

int path[MAXN];
int pathSize = 0;

void printPath()
{
printf("[");
for(int i = 0; i < pathSize; i++)
{
if(i > 0)
{
printf(",");
}
printf("%d", path[i]);
}
printf("]\n");
}

void dfs(int* nums, int numsSize, int start)
{
printPath();

for(int i = start; i < numsSize; i++)
{
    path[pathSize++] = nums[i];

    dfs(nums, numsSize, i + 1);

    pathSize--;
}

}

int main()
{
int nums[] = {1, 2, 3};
int numsSize = 3;

dfs(nums, numsSize, 0);

return 0;

}
8. LeetCode 78 核心写法

LeetCode C 返回二维数组比较麻烦，先记核心逻辑：

void dfs(int* nums, int numsSize, int start)
{
savePath();

for(int i = start; i < numsSize; i++)
{
    path[pathSize++] = nums[i];

    dfs(nums, numsSize, i + 1);

    pathSize--;
}

}

真正完整返回二维数组时，需要：

returnSize
returnColumnSizes
ans

但核心不变。

9. 子集型和普通 DFS 的区别

普通 DFS：

访问节点

子集型回溯：

枚举选择方案

普通 DFS：

visited[u] = 1;
dfs(v);

子集回溯：

path[pathSize++] = nums[i];
dfs(i + 1);
pathSize--;

关键多了：

撤销选择
10. 子集型常见变形
78 子集
无重复元素
直接 dfs(start)
90 子集 II
有重复元素
先排序
同一层跳过重复

核心剪枝：

if(i > start && nums[i] == nums[i - 1])
{
continue;
}
131 分割回文串
也是子集型
只不过每次选的不是单个元素
而是一段字符串
11. 易错点

1. 保存答案的位置

子集型一般一进入 dfs 就保存 path。

2. dfs(i + 1)

不是 dfs(start + 1)。

因为当前选的是 i，下层要从 i 后面开始。

3. pathSize--

递归回来必须撤销选择。

4. 子集顺序不重要

输出顺序不同通常也算对。

5. 有重复元素时要排序 + 同层去重。
6. 最终总结
   子集型回溯

问题：
每个元素选或不选

核心：
path 保存当前选择
start 表示下一个从哪里开始选

模板：
保存 path
for i from start to numsSize-1
选择 nums[i]
dfs(i+1)
撤销 nums[i]

关键词：
path
start
dfs(i+1)
pathSize--

一句话：

子集型回溯 = 当前 path 先保存，然后枚举后面还能选谁。