回溯理论什么是回溯

回溯顾名思义返回溯源记录当前节点后返回前一节点继续的过程。本质上是一种罗列所有情况的穷举搜索。递归递归函数间接或者直接调用自身回到最初最简单的情况。目前的情况归根结底就是一棵树的情况。回溯与递归为什么说回溯常常伴随递归递归是把一棵大二叉树返回到一个最基本的三个节点的树在每一次树变小的过程中都有一个数的子树返回根节点的过程。n个数中k个数的组合问题1.返回值问题:返回值必须与返回类型相匹配-12.私有成员变量的作用域问题核心代码模式下不管声明为private、public还是protected,都属于类内所以可以访问。private:类内访问protected类内和派生类访问public:类内、派生类和类外都可以访问。代码class Solution { private: vectorint vec; vectorvectorint res; public: void backTrack(int n, int k, int startIndex) { if (vec.size() k) { res.push_back(vec); return; } for (int i startIndex; i n-(k-vec.size()1); i) { vec.push_back(i); backTrack(n, k, i 1); vec.pop_back(); } } vectorvectorint combine(int n, int k) { backTrack(n, k, 1); return res; } };总结组合相当于把K层循环的过程用递归来实现。树的宽度要遍历的数组中的每一个元素是循环的第一层。k个不相同数相加为n的组合思路1.递归函数的返回值和参数返回值是void类型参数是传入的n与k。以及用sum记录当前的和。2.终止条件相加为n且是k个数3.单层递归的逻辑一层循环下面每次sumi压入回溯过程和处理过程一一对应。代码class Solution { public: vectorint path; vectorvectorint res; void backtrack(int n, int k,int sum, int startIndex) { if (sum npath.size()k) { res.push_back(path); return; } for (int i startIndex; i 9; i) { sum i; path.push_back(i); backtrack(n, k, sum, i 1); sum - i; path.pop_back(); } } vectorvectorint combinationSum3(int k, int n) { int sum0; backtrack(n,k,sum,1); return res; } };电话键有限数字对应的字母组合思路1.建立数字与字母的映射关系const string lettermap[10]{,,}2.树的宽度与递归的深度3.回溯过程结果用一个字符串string s和一个字符串数组vector res保存1确定返回值void和参数digits,int index;2确定终止条件string的长度和digit的长度相等digits.size()index3单层循环逻辑压入--遍历--弹出代码class Solution { public: vectorstring res; string path; const string lettermap[10] {,, ,, abc, def, ghi, jkl, mno, pqrs, tuv, wxyz}; void backTrack(stringdigits, int index) { if (index digits.size()) { res.push_back(path); return; } // 建立数字--字母映射 int digit digits[index] - 0; // 把字符类型转化为int; string letters lettermap[digit]; // 建立数字和字母的对应关系; for (int i 0; i letters.size() ; i) { path.push_back(letters[i]); backTrack(digits, index 1); path.pop_back(); } } vectorstring letterCombinations(string digits) { backTrack(digits, 0); return res; }