提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
文章目录
一、回溯算法理论基础
有递归就有回溯,回溯算法是纯暴力搜索。回溯的本质是穷举,穷举所有可能,然后选出我们想要的答案。
回溯算法可以解决:组合问题、切割问题、子集问题、排列问题、棋盘问题(N皇后、解数独等)。
回溯法解决的都是在集合中递归查找子集,集合的大小就构成了树的宽度,递归的深度构成的树的深度。因此回溯法都可以抽象成一个N叉树结构。
回溯算法模版:
void backtracking(参数) {
if (终止条件) {
收集结果;
return;
}
for (集合元素) {
处理结点;
递归函数;
回溯操作;
}
}
二、77组合
class Solution {
public:
void dfs(vector<vector<int>>& res, vector<int>& path, int n, int k) {
if (path.size() == k) {
res.push_back(path);
return;
}
int startNum = 0;
if (path.size() > 0) {
startNum = path[path.size()-1];
}
for (int i = startNum + 1; i <= n; i ++) {
path.push_back(i);
dfs(res, path, n, k);
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> path;
dfs(res, path, n, k);
return res;
}
};
剪枝优化:
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void dfs(int n, int k, int startNum) {
if (path.size() == k) {
res.push_back(path);
return;
}
for (int i = startNum; i <= (n - (k - path.size()) + 1); i ++) {
path.push_back(i);
dfs(n, k, i + 1);
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
dfs(n, k, 1);
return res;
}
};