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