前言

回溯描述。

一、核心概念

  • 在深度优先搜索（DFS）的递归过程中回溯：回溯问题可抽象为树形结构，递归向下处理和获取结果，回溯向上撤销结果
  • 相对于暴力算法，是一种间接/有技巧（使用递归代替多重循环）的暴力搜索/穷举，不高效

二、典型问题

分类依据：代码随想录 (programmercarl.com)和力扣

  • 组合问题：N个数里面按一定规则找出k个数的集合
  • 切割问题：一个字符串按一定规则有几种切割方式
  • 子集问题：一个N个数的集合里有多少符合条件的子集
  • 排列问题：N个数按一定规则全排列，有几种排列方式
  • 图问题：图中使用深度优先遍历
  • 棋盘问题：N皇后，解数独等等

三、算法步骤

  1. 将回溯问题抽象为树形结构
  • 问题规模为树的宽度
  • 递归深度为树的深度
  1. 确定回溯函数的参数和返回值
  • 可依据逻辑需要后补充参数

可能的参数：
候选集合
问题规模为树的宽度width
递归深度为树的深度depth
当前结点问题规模的起始索引start_index
标记集合中元素是否已选取的数组
结果集合res和results

  • 返回值一般为空（void）
  1. 确定回溯函数的终止条件和获取结果逻辑
  • 在树的叶子结点获取结果
  • 在树的叶子结点结束当前层递归，并回溯撤销结果

注意：子集问题，在树的每结点获取结果

  1. 确定回溯函数的遍历和处理结果逻辑
  • 横向遍历当前树层各结点的问题规模
  • 纵向递归处理结果

四、模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 0. 将回溯问题抽象为树形结构
// 1. 确定回溯函数的参数和返回值
void backtrack(参数) 
{
	// 2. 确定回溯函数的终止条件和获取结果逻辑
    if (终止条件) 
    {
        获取结果;
        
        return;
    }

	// 3. 确定回溯函数的遍历和处理结果逻辑
    for (当前树层，各结点的问题规模) 
    {
        处理结果;
        
        backtrack(参数); // 递归
        
        撤销结果; // 回溯
    }
}

五、模板示例

77.组合 - 力扣（LeetCode）——中等的题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution
{
private:
    // 0. 将回溯问题抽象为树形结构
    vector<int> res;
    vector<vector<int>> results;

    // 1. 确定回溯函数的参数和返回值
    void backtrack(int width, int depth, int start_index)
    {
        // 2. 确定回溯函数的终止条件和获取结果逻辑
        if (res.size() == depth)
        {
            results.push_back(res);

            return;
        }

        // 3. 确定回溯函数的遍历和处理结果逻辑
        for (int i = start_index; i <= width; ++i)
        {
            res.push_back(i);       // 处理结果

            backtrack(width, depth, i + 1); // 递归

            res.pop_back(); // 撤销结果  回溯
        }
    }

public:
    vector<vector<int>> combine(int n, int k)
    {
        backtrack(n, k, 1);

        return results;
    }
};

六、性能分析

时间复杂度：指数级

组合问题：

  • 时间复杂度：一般为：组合规模 × 每组合判断并加入结果集的时间

如：$O(\complement^n_m × n)$。从m规模中取n规模，有$\complement^n_m$种组合；每组合判断并加入结果集的时间需要O(n)

如：$O(2^n × n)$。从n规模中取或不取，有$2^n$种组合；每组合判断并加入结果集的时间需要O(n)

  • 空间复杂度：一般为：递归栈规模 + 结果集规模：$O(n)$。n为数据规模

切割和子集问题：类似组合问题

排列问题：全排列

  • 时间复杂度：一般为：全排列规模 × 每排列判断并加入结果集的时间：$O(n!×n)$。n为数据规模

参见：
回溯算法入门级详解 + 练习（持续更新） - 全排列 - 力扣（LeetCode）
本周小结！（回溯算法系列三） | 代码随想录 (programmercarl.com)

  • 空间复杂度：类似组合问题

图和棋盘问题：具体问题具体分析

七、优化方法

1. 剪枝

作用：降低时间复杂度

描述：

  • 不符合条件的问题
  • 不再继续处理并获取结果

形式：

  • 横向剪枝：缩小当前树层各结点的问题规模：修改for()循环

  • 纵向剪枝：增加终止条件

模板示例：216.组合总和 III - 力扣（LeetCode）——中等的题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution
{
private:
    // 0. 将回溯问题抽象为树形结构
    vector<int> res;
    vector<vector<int>> results;

    // 1. 确定回溯函数的参数和返回值
    // width：[1,9]
    void backtrack(int depth, int target_sum, int start_index, int sum)
    {
        // 2. 确定回溯函数的终止条件和获取结果逻辑
        if (sum > target_sum) // 纵向剪枝
        {
            return;
        }

        if (res.size() == depth)
        {
            if (sum == target_sum)
            {
                results.push_back(res);

                return;
            }

            return;
        }

        // 3. 确定回溯函数的遍历和处理结果逻辑
        for (int i = start_index; i <= 9 - (depth - res.size()) + 1; ++i) // 横向剪枝
        {
            sum += i;
            res.push_back(i); // 处理结果

            backtrack(depth, target_sum, i + 1, sum); // 递归

            sum -= i;
            res.pop_back(); // 撤销结果  回溯
        }
    }

public:
    vector<vector<int>> combinationSum3(int k, int n)
    {
        backtrack(k, n, 1, 0);

        return results;
    }
};

八、其他技巧

1. 元素不可以和可以重复选取

  • 在同一集合中，若元素不可以重复选取，则在递归时，修改当前结点问题规模的起始索引start_index

如：77.组合 - 力扣（LeetCode）——中等

  • 在同一集合中，若元素可以重复选取，则在递归时，不修改当前结点问题规模的起始索引start_index

如：39.组合总和 - 力扣（LeetCode）——中等

2. 从同一集合中取和从不同集合间取元素

  • 从同一集合中取元素，需要参数：当前结点问题规模的起始索引start_index

如：77.组合 - 力扣（LeetCode）——中等

  • 从不同集合间取元素，可能不需要参数：当前结点问题规模的起始索引start_index

如：17.电话号码的字母组合 - 力扣（LeetCode）——中等

3. 求和问题

  • 在求和问题中，可能需要先排序后剪枝

如：39.组合总和 - 力扣（LeetCode）——中等

4. 先排序后去重

排序后才可以，通过相邻元素判断是否重复选取

  • 树层去重

参见：代码随想录 (programmercarl.com)

如：40.组合总和 II - 力扣（LeetCode）——中等

如：47.全排列 II - 力扣（LeetCode）——中等

  • 树枝去重

如：47.全排列 II - 力扣（LeetCode）——中等

排列问题可以在树层去重，也可以在树枝去重；但在树层去重效率更高。参见：代码随想录 (programmercarl.com)

5. 去重的方式

去重：即标记集合中元素是否已选取

  • 数组
  • 编程语言内置的哈希表数据结构（有频繁的插入、映射、查找和删除操作，时间和空间复杂度高）。如：C++的unordered_set
  • 哈希数组（已知数据规模）

参见：代码随想录 (programmercarl.com)

6. 组合、切割、排列和子集问题的区别

  • 组合、切割和排列问题，树的叶子结点为结果（遍历符合条件的树枝）

  • 子集问题，树的每个结点为结果（遍历树）；所以可以不需要确定回溯函数的终止条件，不存在剪枝的优化方法

7. 组合、切割、子集和排列问题的区别

  • 组合问题、切割和子集问题，集合是无序的，for()循环从当前结点问题规模的起始索引start_index开始；可能需要去重

  • 排列问题，集合是有序的，for()循环从0开始，必需去重

8. 二维横向遍历

  • 在二维横向遍历中
  • 进行递归和回溯

如：37.解数独 II - 力扣（LeetCode）——困难

九、力扣例题

组合问题：

  • 77.组合——中等
  • 216.组合总和 III——中等
  • 17.电话号码的字母组合——中等
  • 39.组合总和——中等
  • 40.组合总和 II——中等

切割问题：

  • 131.分割回文串——中等
  • 93.复原 IP 地址——中等

子集问题：

  • 78.子集——中等
  • 90.子集 II——中等
  • 491.递增子序列——中等

排列问题：

  • 46.全排列——中等
  • 47.全排列 II——中等

其他问题：

  • 332.重新安排行程——困难

图问题：

  • 51.N 皇后——困难
  • 37.解数独——困难

总结

回溯描述。

参考资料