代码随想录——回溯

系列文章目录

代码随想录——回溯

---

---

概述

回溯的本质就是递归遍历，但在完成某一条路之后会撤回到上一层，然后重新选择另一条路继续遍历，是一个比较低效的算法，能进行提升的方式就是剪枝。

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

组合

组合

链接：https://leetcode.cn/problems/combinations/description/

vector<vector < int > > 作为最终返回的结果，vector < int >作为每一小项，中止条件是vector< int > == k，注意在递归过程中n，k是不变的，所以必须引入一个递增index来去重。

剪枝方法：

1. 已经选择的元素个数：path.size();
2. 还需要的元素个数为: k - path.size();
3. 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

组合III

链接：https://leetcode.cn/problems/combination-sum-iii/description/

与前一个组合几乎一样，但中止条件需要加一个total == k的判断。

电话号码的字母组合

链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/

中止条件是单个项的size等于digits的size，一开始我以为要双循环，即digits遍历和单个数字对应的字母遍历，但其实不需要，因为digits一定是顺序往后取的，所以只需要定义一个index，每层递归+1即可。
ps：在leetcode由char转变为int的方法是减去 ‘0’

num[digits[index] - '0'

组合总和

链接：https://leetcode.cn/problems/combination-sum/description/
中止条件为当总和相等时push进result并return，总和超过target时直接人return；注意这道题也是不能重复的，一般不能重复的都需要加入index来保证起始位置。

组合总和II

链接：https://leetcode.cn/problems/combination-sum-ii/description/
这道题不重复的核心点在于，同层的数不能够重选，例如[1,1,2,2,5]，第一层选了1，第二层还是可以继续选1，因为两者不是同层的。但如果第一层的第一个1用完了，又选了第二个1，这就重复了，所以只需要加一个判断条件：

            if (i > index && candidates[i] == candidates[i - 1]) {
                continue;
            }

这里的核心点在于?i > index，因为index是本层的第一个数，必然不可能重复，所以要从index下一个开始判断，此时如果第二个数和第一个数是相同的，则属于同层重复选择，直接continue；

分割

分割回文串

https://leetcode.cn/problems/palindrome-partitioning/description/
每切下来一个子字符串，就相当于是在一层做了选择，这样就可以套上回溯算法的模板。中止条件是起始切割位置到了字符串的最后一位，额外再写一个回文判断函数。、
注意：leetcode里常用的切割字符串函数substr，第一个参数是起始位置，第二个参数是要切割的长度。

string str = s.substr(index,i - index + 1);

** 复原ip地址

https://leetcode.cn/problems/restore-ip-addresses/description/
这道题一直做错，能接受的方法是，将切割每一个子字符串进行判断，符合标准后放入vector备用，个数达到4个并且index也等于s.size()之后，再拼接放入最终的result里。
注意：string转为int直接用stoi函数

return stoi(s) <= 255;

字符串的增加和删改不能用-=和+=，要用insert和erase。

子集

子集

https://leetcode.cn/problems/subsets/description/
这道题唯一要注意的点是子集的大小是不固定的，所以不能在中止条件里面将子集添加到结果里，每一次循环都要添加，所以放在递归的开头。中止条件是index == s.size()。

子集II

https://leetcode.cn/problems/subsets-ii/description/
这题和之前组合的去重思路一模一样，在子集的基础上，首先对nums进行sort保证是递增的，然后进行判断去掉本层重复的选择。

if(i > index && nums[i] == nums[i - 1]) continue;