backtrack-回溯搜索算法总结

backtrack——回溯算法总结

这几天着重在刷LeetCode有关回溯搜索算法的题，之前也写了一些博客，感觉当时清楚，但是原理上还是有点模糊。之前根据别人的模板，依葫芦画瓢，解决了一些问题，但是有的时候条件变了，就有点理不清楚了，特别是哪里该加一些限制条件，很懵逼。所以总结了一下。

1. 到底什么是回溯？

回溯算法，都知道是基于递归的算法。那为什么要用递归呢，可以用传统的写法代替嘛？之所以用递归，就是因为如果用传统的方式，很难写或者根本写不出来。举个例子，比如我们想知道用集合nums = [1, 2, 3]中的三个数字（可重复）一共能构成多少个不同的三位数，学过排列组合的都知道一共有27（3的3次方）种：(1,1,1), (1,1,2), (1,1,3), (2,1,1), (2,1,2), (2,1,3)…(3,3,3) 。用最传统的方式，都会写，用一个三层的for循环来写：

vector<vector<int>> res;
vector<int> path;
for (int i = 0; i < 3; i++) {
	for (int j = 0; j < 3; j++) {
	 	for (int k = 0; k < 3; k++) {
	 		path.push_back({ nums[i], nums[j], nums[k] });
	 		res.push_back(path);
	 	}
	 }
}

这个例子中，集合中的元素还很少。那么如果集合中有100个元素呢？传统方式是不是要写100层循环？1000呢？因此，这种情况下单靠循环是完成不了的。这种情况下，就需要递归出场了。上面的代码可以写为如下递归的形式：

vector<vector<int>> res;
vector<int> path;
void backtrack_0(vector<int>& nums,  vector<vector<int>> &res) {
	if (path.size() == nums.size()) {
		res.push_back(path);
		return;
	}
	// else
	for (int i = 0; i < nums.size(); i++) {
		path.push_back(nums[i);
		backtrack_0(nums, res);
		path.pop_back();
	}
}

上面的代码中，path的长度其实就是循环的深度，回溯递归里的每一层其实都是一个循环；而else部分，则相当于每层循环的方式（每层for循环该怎么写）。递归其实就模拟了上诉过程。

如果题目变成了三个数字加起来能构成不同的和的情况有多少（就是前面用过的数，后面不能再用。比如：112和211的和就是一样的）？那么该怎么改呢？
传统的写法：

for (int i = 0; i < 3; i++) {
	for (int j = i; j < 3; j++) {
	 	for (int k = j; k < 3; k++) {
	 		path.push_back({ nums[i], nums[j], nums[k] });
	 		res.push_back(path);
	 	}
	 }
}

对应的递归写法：

vector<vector<int>> res;
vector<int> path;
void backtrack_1(vector<int>& nums,  vector<vector<int>> &res, int idx) {
	if (path.size() == nums.size()) {
		res.push_back(path);
		return;
	}
	// else
	for (int i = idx; i < nums.size(); i++) {
		path.push_back(nums[i);
		backtrack_1(nums, res, i);
		path.pop_back();
	}
}

最后的输出都一样：[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 2, 3], [1, 3, 3], [2, 2, 2], [2, 2, 3], [2, 3, 3], , [3, 3, 3]。
同时，从这里可以看到：循环的起始范围变了：从0变成了上层循环的循环变量；而在回溯函数中，循环的起始值也从0变为了idx。说明，回溯跟多层循环有着非常密切的关系！终止条件跟循环层数有关系，递归函数里面的循环跟每层循环又有着非常紧密的联系！