算法训练营第24天|回溯算法理论基础 LeetCode 77.组合

终于把二叉树做完了！开始新的篇章，回溯！

回溯算法理论基础

回溯算法题目分类：

1.组合

2.分割

3.子集

4.排列

5.棋盘问题

什么是回溯？

回溯叫做回溯搜索法，是一种搜索方式。回溯是递归的副产品，有递归就会有回溯。

LeetCode 77.组合

题目链接：

77. 组合 - 力扣（LeetCode）

解题思路：

void backtracking(参数){if (终止条件){存放结果；return；}
}for(选择：本层集合中元素个数){处理对应的节点；backtracking（参数）；//递归回溯，撤销处理的结果;
}

代码：

class Solution {
public:vector<vector<int>>result;vector<int>path;void backtracking(int n,int k, int Index){if(path.size()==k) {result.push_back(path);return;}for(int i=Index;i<=n;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 result;}
};