回溯算法

介绍：回溯算法的核心是递归函数，它是一种暴力穷举的算法，并不是一种高效算法。如果我们想想对回溯算法进行一下优化，可以在其基础上加一些剪枝的操作，但不能改变它穷举的本质。虽然它不高效，但一些题只能通过穷举所有的可能，并从中选出想要的结果

能解决的问题类型：

  1. 组合问题：N个数里面按一定规则找出k个数的集合
  2. 切割问题：一个字符串按一定规则有几种切割方式
  3. 子集问题：一个N个数的集合里有多少符合条件的子集
  4. 排列问题：N个数按一定规则全排列，有几种排列方式
  5. 棋盘问题：N皇后，解数独等等

将回溯问题抽象成一棵树

能用回溯法解决的问题都可以抽象为树形结构（无一例外），因为这些问题的本质都是在给定的集合中通过递归获取我们需要的结果，其中集合的大小构成树的宽度，而递归的深度便构成树的深度，而递归函数要有终止条件，所以抽象出来的树必定是一颗高度有限的树。所以我们在平常解决这些问题的时候，为了方便理解，可以在草稿纸上将这棵树画出来

回溯算法模板

回溯三部曲：

  1. 确定递归函数返回值以及参数

    回溯算法的函数返回值一般为void，需要的参数有时候不容易定下来，所以一般是先写逻辑再确定需要的参数

  2. 确定搜索的遍历过程

    回溯算法一般是在集合中递归搜索，集合的大小构成树的宽度，递归的深度构成树的深度，如图所示：

    此图以leetcode的77题:组合为例

    遍历过程的伪代码形式：

    1
    2
    3
    4
    5
    for (选择：本层集合中元素) {
    		处理节点;
    		backtracking(路径，选择列表);
    		回溯，撤销处理结果;
    }

    核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，其中for循环控制横向遍历，backtracking（递归函数）控制纵向遍历，如此便能把一棵树的节点全遍历完

  3. 确定终止条件

    如上图所示，一般来说，当纵向遍历到叶子结点时，就代表着找到了满足条件的一个结果，将这个结果存起来并结束本层递归

    终止条件伪代码：

    1
    2
    3
    4
    if (终止条件) {
    	存放结果;
    	return;
    }

通过上面的分析我们可以得到回溯算法模板框架：

1
2
3
4
5
6
7
8
9
10
11
12
13
void backtracking(参数)
{
	if (终止条件) {
		存放结果;
		return;
	}

	for (选择：本层集合中元素) {
		处理节点;
		backtracking(路径，选择列表);
		回溯，撤销处理结果;
	}
}

回溯算法的时间复杂度取决于结果集的大小，即满足条件的组合的个数，这里有一个通用公式：路径长度×搜索树的叶子数

现在我们便通过用该模板来解决一道问题来加深理解

leetcode题目链接：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
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        std::vector<int> path;      // 存放k个元素
        std::vector<std::vector<int>> result;    // 存放结果集 
        //回溯经典模板
        std::function<void(int)> dfs = [&](int i) {
            if (k == path.size()) {              //递归退出条件，即到达决策树底层
                result.emplace_back(path);       //将每个符合要求的组合存入result中
                return;
            }

            for (; i <= n; i++) {         //for循环控制横向遍历，选择：本层集合中元素
                path.emplace_back(i);     //将当前元素放入
                dfs(i + 1);               //递归控制纵向遍历
                path.pop_back();          //回溯，撤销处理结果
            }
        };

        dfs(1);      //开始递归
        return result;
    }
};

时间复杂度：O(K⋅C(n,k))

空间复杂度：O(K)

剪枝

回溯算法虽是暴力搜索，但它是可以根据一些隐藏条件进行小优化的。以上面的那道题为例，当n = 4，k = 3时，在第一层for循环的元素3之后（包括3）的遍历便没有必要了，换句话说也就是第一层for循环最多只能到2。而第一层节点为1时，第二层for循环的元素4也没有必要遍历到，如图：

此图以n=4，k=4时为例

所以我们可以将这些没必要遍历的枝干剪掉来优化算法，而我们的优化其实就是针对for循环里的范围进行思考。以上题为例，我们可以通过逐步思考以下两个问题来进行缩小范围

1.每次选取后还需选取多少元素？ k - path.size();

2.还需要选取的元素个数最多能从哪里进行纵向搜索？ n - (k - path.size()) + 1;

为什么有个+1呢？因为要包括起始位置

上题剪枝后的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    std::vector<std::vector<int>> combine(int n, int k) {
        std::vector<int> path;
        std::vector<std::vector<int>> result;

        std::function<void(int)> dfs = [&](int i) {
            if (k == path.size()) {
                result.emplace_back(path);
                return;
            }

            for (; i <= n - (k - path.size()) + 1; i++) {
                path.emplace_back(i);
                dfs(i + 1);
                path.pop_back();
            }
        };

        dfs(1);
        return result;
    }
};