面试热点题：回溯算法之组合 组合与组合总和 III

什么是回溯算法？

回溯算法也可以叫回溯搜索算法，回溯是递归的"副产品",回溯的本质是穷举，然后选出我们需要的数据，回溯本身不是特别高效的算法，但我们可以通过"剪枝"来优化它。

理解回溯算法

回溯算法的解决可以模拟成树的结构，因为回溯法解决的是在集合中递归搜索子集的过程，集合的大小构成树的宽度，递归的深度构成树的深度。

回溯算法模板

1. 确定回溯算法的返回值与参数(一般先写逻辑，然后需要什么参数，就增加什么参数)
2. 确定回溯函数的终止条件
3. 确定回溯搜查的遍历过程

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

组合

问题：
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
来源：力扣（LeetCode）组合

思路一：这种题目我们一眼就能想到使用for循环套循环比如 k==2时

	int n = 4;for (int i = 1; i <= n; i++){for (int j = i + 1; j <= n; j++){//处理结果}}

但是如果k越来越大，我们套用的循环也会越来越多，这种暴力解法无疑是不现实的。

思路二：我们在前面说过，可以使用树的结构来模拟回溯递归的过程：
比如n=4 k=2

树的初始集合是[1,2,3,4],从左向右取，取过的数不再取，每次从集合中选取元素，可选择的范围逐渐缩小。有图可以发现，n相当于树的宽度，而k相当于树的深度。我们再由模板来写出最终代码：

class Solution {
public:vector<vector<int>> arr;//存放符合条件的集合vector<int> _arr;//用来存放符合条件的单一数据void BackTracking(int n, int k, int begin){if (_arr.size() == k)//递归终止条件{arr.push_back(_arr);//单一数据存放至总集合里return;}for (int i = begin; i <= n; i++)//控制树的横向遍历{_arr.push_back(i);//处理节点BackTracking(n, k, i + 1);//递归，控制树的纵向遍历，即深度_arr.pop_back();//回溯，撤销处理的节点}}vector<vector<int>> combine(int n, int k) {BackTracking(n, k, 1);return arr;}
};

剪枝优化

如果出现下面情况：
n=4 k=4
那么在第一层for循环中，从元素2开始的遍历都没有意义，因为满足k的数量不够了，所以有图可知，打叉的地方都可以优化掉

优化过程：

1. 已经选择的元素个数：_arr.size()
2. 还需要的元素个数：k - _arr.size()

优化后的代码：

class Solution {
public:vector<int> _arr;vector<vector<int>> arr;void BackTracking(int n, int k, int begin){if (_arr.size() == k){arr.push_back(_arr);return;}for (int i = begin; i <= n-(k-_arr.size())+1; i++)//剪枝优化{_arr.push_back(i);BackTracking(n, k, i + 1);_arr.pop_back();}}vector<vector<int>> combine(int n, int k) {BackTracking(n, k, 1);return arr;}
};

组合总和 III

问题：
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
来源：力扣（LeetCode）组合总和 III

思路：这个题相对于上一个题来说，就是k为树的深度，而集合固定为1到9，也就是树的宽度为9
比如：k=2 只取两个数

代码：

class Solution {
public:vector<vector<int>> arr;vector<int> _arr;void BackTracking(int k,int n,int begin,int sum){if(_arr.size()==k)//终止条件{if(sum==n)//满足题意{arr.push_back(_arr);}return;}for(int i=begin;i<=9;i++)//横向遍历{sum+=i;//收集元素总和_arr.push_back(i);//收集元素BackTracking(k,n,i+1,sum);//递归，纵向遍历sum-=i;//回溯_arr.pop_back();//回溯}}vector<vector<int>> combinationSum3(int k, int n) {BackTracking(k,n,1,0);return arr;}
};

剪枝优化

如果我们选择的元素总和已经大于n，那么我们再往后遍历的总和肯定也大于n，就没有继续遍历下去的意义了。元素个数方面，同样与上一题一样能继续优化。

优化后：

class Solution {
public:vector<vector<int>> arr;vector<int> _arr;void BackTracking(int k,int n,int begin,int sum){if(sum>n)//剪枝条件{return;}if(_arr.size()==k){if(sum==n){arr.push_back(_arr);}return;}for(int i=begin;i<=9-(k-_arr.size())+1;i++)//元素个数的优化{sum+=i;_arr.push_back(i);BackTracking(k,n,i+1,sum);sum-=i;_arr.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {BackTracking(k,n,1,0);return arr;}
};