代码随想Day24 | 回溯法模板、77. 组合

理论基础 

回溯法和递归不可分割，回溯法是一种穷举的方法，通常需要剪枝来降低复杂度。回溯法有一个选择并退回的过程，可以抽象为树结构，回溯法的模板如下：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

 77. 组合  

这道题是回溯的经典题目，按照递归三步走：

参数：

在这里要定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合。函数里一定有两个参数，既然是集合n里面取k个数，那么n和k是两个int型的参数。

然后还需要一个参数，为int型变量startIndex，这个参数用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,...,n] ）。

回溯函数结束条件：

path这个数组的大小如果达到k，说明我们找到了一个子集大小为k的组合了，此时用result二维数组，把path保存起来，并终止本层递归。

单层搜索的过程

回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出for循环用来横向遍历，递归的过程是纵向遍历。

如此我们才遍历完图中的这棵树。for循环每次从startIndex开始遍历，然后用path保存取到的节点i。可以看出backtracking（递归函数）通过不断调用自己一直往深处遍历，总会遇到叶子节点，遇到了叶子节点就要返回。backtracking的下面部分就是回溯的操作了，撤销本次处理的结果。

此外：比较重要的剪枝部分：

可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。

如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。注意代码中i，就是for循环里选择的起始位置。

for (int i = startIndex; i <= n; i++) {

优化过程如下：

1. 已经选择的元素个数：path.size();

2. 还需要的元素个数为: k - path.size();

3. 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。

最终详细代码如下：

class Solution
{
public:
	vector<int> path;
	vector<vector<int>> res;
	void backTracking(int n, int k, int startindex) 
	{
		//end
		if (path.size() == k) 
		{
			res.push_back(path);
			return;
		}
		// backtracking
		for (int i = startindex; i <= n - (k - path.size()) + 1; i++) 
		{
			path.push_back(i);
			backTracking(n, k, i + 1);
			path.pop_back();
		}
	}
	vector<vector<int>> combine(int n, int k) 
	{
		backTracking(n, k, 1);
		return res;
	}
};