网站建设运营合同,阿里云轻量级wordpress,网站上传附件目录格式,qq推广群号码大全理论基础 回溯法和递归不可分割#xff0c;回溯法是一种穷举的方法#xff0c;通常需要剪枝来降低复杂度。回溯法有一个选择并退回的过程#xff0c;可以抽象为树结构#xff0c;回溯法的模板如下#xff1a; void backtracking(参数) {if (终止条件) {存放结果;return;}… 理论基础 回溯法和递归不可分割回溯法是一种穷举的方法通常需要剪枝来降低复杂度。回溯法有一个选择并退回的过程可以抽象为树结构回溯法的模板如下 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) {优化过程如下 已经选择的元素个数path.size(); 还需要的元素个数为: k - path.size(); 在集合n中至多要从该起始位置 : n - (k - path.size()) 1开始遍历 为什么有个1呢因为包括起始位置我们要是一个左闭的集合。举个例子n 4k 3 目前已经选取的元素为0path.size为0n - (k - 0) 1 即 4 - ( 3 - 0) 1 2。 最终详细代码如下 class Solution
{
public:vectorint path;vectorvectorint res;void backTracking(int n, int k, int startindex) {//endif (path.size() k) {res.push_back(path);return;}// backtrackingfor (int i startindex; i n - (k - path.size()) 1; i) {path.push_back(i);backTracking(n, k, i 1);path.pop_back();}}vectorvectorint combine(int n, int k) {backTracking(n, k, 1);return res;}
};
