回溯例题：组合型剪枝

组合型回溯笔记
康康灵神思路
方法一：枚举下一个数选哪个
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. 组合
78. 组合总和 III
79. 括号生成
80. 组合总和

最基础例子：

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

6. 总结
   组合型回溯

问题：
从 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 时保存。