组合型回溯笔记
康康灵神思路
方法一：枚举下一个数选哪个
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans = []
        path = []

        # 枚举选哪个：在 1 到 i 中选一个数，加到 path 末尾
        def dfs(i: int) -> None:
            d = k - len(path)  # 还要选 d 个数
            if d == 0:  # 选好了
                ans.append(path.copy())
                return

            # 枚举的数不能太小，否则后面没有数可以选
            for j in range(i, d - 1, -1):
                path.append(j)
                dfs(j - 1)
                path.pop()  # 恢复现场
        dfs(n)  # 从 n 开始倒着枚举
        return ans

复杂度分析
时间复杂度：分析回溯问题的时间复杂度，有一个简易公式：路径长度×搜索树的叶子数。对于本题，路径长度始终为 k，叶子个数为 C(n,k)，所以时间复杂度为 O(k⋅C(n,k))。
空间复杂度：O(k)。返回值不计入。

方法二：选或不选
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans = []
        path = []

        # 选或不选：讨论 i 是否加入 path
        def dfs(i: int) -> None:
            d = k - len(path)  # 还要选 d 个数
            if d == 0:  # 选好了
                ans.append(path.copy())
                return

            # 不选 i
            if i > d:
                dfs(i - 1)

            # 选 i
            path.append(i)
            dfs(i - 1)
            path.pop()  # 恢复现场

        dfs(n)  # 从 i=n 开始倒着枚举
        return ans
灵神这里是倒着回溯，仅提供从n个里面选k个，d是选定之后还要选的个数
1. 前提条件

组合型问题问的是：

从 n 个数里面选 k 个
求所有组合

典型题：

77. 组合
216. 组合总和 III
22. 括号生成
39. 组合总和

最基础例子：

n = 4, k = 2

答案：

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

2. 核心概念

组合和子集很像，但区别是：

子集型：
    每个长度都要

组合型：
    只要长度为 k 的 path

所以组合型保存答案的位置不是一进 dfs 就保存，而是：

if(pathSize == k)
{
    保存 path;
    return;
}

3. 固定模板
void dfs(int start)
{
    if(pathSize == k)
    {
        保存 path;
        return;
    }

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

        dfs(i + 1);

        pathSize--;
    }
}

核心还是：

选择
递归
撤销

4. 为什么是 dfs(i + 1)

因为组合不看顺序。

[1,2] 和 [2,1] 是同一个组合

所以一旦选了 i，下一层只能从 i+1 往后选，不能回头。

5. 用 n=4,k=2 推一遍

开始：

path=[]
start=1

选 1：

path=[1]

下一层从 2 开始：

选2 -> [1,2] 保存
选3 -> [1,3] 保存
选4 -> [1,4] 保存

回到第一层，选 2：

path=[2]

下一层从 3 开始：

选3 -> [2,3] 保存
选4 -> [2,4] 保存

选 3：

path=[3]

下一层从 4 开始：

选4 -> [3,4] 保存

最终：

[1,2]
[1,3]
[1,4]
[2,3]
[2,4]
[3,4]
6. 剪枝优化

原始循环：

for(int i = start; i <= n; i++)

有时候后面数字不够选了，还会继续递归，浪费。

比如：

n=5, k=3
pathSize=1

还需要：

need = k - pathSize = 2

如果从 i=5 开始，后面只剩一个数 5，不够选 2 个。

这里是正着回溯，也就是说need是还需要选的数，为了保证后面i+1的回溯情况，所以要保持第i个，所以是n-need+1

所以循环可以写成：

int need = k - pathSize;

for(int i = start; i <= n - need + 1; i++)

这个公式很重要：

i 最晚只能到 n - need + 1

7. C 代码打印版
#include <stdio.h>

#define MAXN 30

int path[MAXN];
int pathSize = 0;
int n;
int k;

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

void dfs(int start)
{
    if(pathSize == k)
    {
        printPath();
        return;
    }

    int need = k - pathSize;

    for(int i = start; i <= n - need + 1; i++)
    {
        path[pathSize++] = i;

        dfs(i + 1);

        pathSize--;
    }
}
int main()
{
    n = 4;
    k = 2;

    dfs(1);

    return 0;
}

8. 和子集型对比
子集型：

保存答案：
    一进入 dfs 就保存

原因：
    每个 path 都是答案

循环：
    for i = start to numsSize-1

--------------------------------

组合型：

保存答案：
    pathSize == k 时保存

原因：
    只要长度为 k 的 path

循环：
    for i = start to n - need + 1
9. 易错点
1. 组合型不是一进 dfs 就保存。

2. pathSize == k 才保存。

3. 递归必须是 dfs(i+1)，不能 dfs(start+1)。

4. 组合不看顺序，所以不能回头选。

5. 剪枝公式：
   i <= n - (k - pathSize) + 1

10. 总结
组合型回溯

问题：
    从 n 个数里选 k 个

核心：
    pathSize == k 时保存答案

变量：
    start 表示下一层从哪里开始选
    pathSize 表示当前选了几个
    k 表示目标数量

模板：
    if(pathSize == k)
        保存答案

    for i from start to n - need + 1
        选择 i
        dfs(i+1)
        撤销 i

主要还是考虑need和k和pathSize的关系从而实现减小范围剪枝
    start
    k
    pathSize
    need
    剪枝

组合型回溯 = 固定长度的子集，只在 pathSize == k 时保存。