算法训练day27 回溯算法概述、LeetCode77.
回溯算法
-
与递归函数联系,是一种纯暴力搜索方式
-
解决问题(抽象为树形结构
- 组合问题(无序
- 切割问题
- 子集问题
- 排列问题(有序
- 棋盘问题(n皇后、解数独
-
回溯算法模板
-
void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) { 处理节点; backtracking(路径,选择列表); // 递归 回溯,撤销处理结果 } }
-
77.组合
题目
题解
-
class Solution { private: vector<vector<int>> result; // 存放结果集合 vector<int> path; // 存放符合条件的结果 void backtracking(int n, int k, int startIndex) { if (path.size() == k) { result.push_back(path); return; } for (int i = startIndex; i <= n; i++) { path.push_back(i); backtracking(n, k, i + 1); path.pop_back(); } } public: vector<vector<int>> combine(int n, int k) { result.clear(); path.clear(); backtracking(n, k, 1); return result; } };
-
将组合的方式以树形组合起来,递归下去,处理数据收集结果,回溯回来