算法（一）--回溯
算法（一）--回溯
前言
本心得会将常见的算法解题思路按模块进行拆分讲解。模块分别是：双指针、链表、二叉树、回溯、二分查找、栈堆、贪心、动态规划、图论。斯认为新接触到一道算法题时，可以尝试将其识别为某模块的题目，应用相应模块的通用解法进行解题。但具体问题具体分析，通用解法只是提供一个启发，需要我们在不断的刷题中磨砺手感和技巧。
回溯算法
回溯算法本质上是暴力穷举算法，和我们常见的深度搜索算法DFS算法非常相似。DFS算法会放在二叉树或者图论进行深入的讲解，这里不做过多的介绍。有一句话我认为解读的非常到位，回溯是纵向遍历，for是横向遍历。for遍历我们非常熟悉，比如现在有一个二维数组。for循环遍历该数组结果就是1234123412341234。那如果是回溯遍历呢，那就是1111222233334444，这就是纵向遍历。使用回溯遍历解决的问题，可以称为回溯问题。回溯问题一般可以抽象为一颗决策树，决策树的叶子节点存放着一个合法答案，如何得到这个叶子节点呢，就是进行纵向搜索。
设计一个回溯算法需要解决三个问题，称为回溯三要素：
- 递归函数参数
- 递归终止条件
- 单层搜索逻辑
这里先给出回溯算法的模版：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<vector<T>> result;
vector<T> path;
void backtrace(..., path, result) {
if bool {
result.push_back(path);
}
for 选择 in 选择列表 {
判断是否是想要的、做决策
backtrace(..., path, result);
撤销决策
}
}
什么叫做决策呢？这里需要根据不同的题目进行具体问题具体分析。这里做的事情其实就是更新path，path记录了部分符合需求的数据，但还没达到要求，需要再做决策这里进行实时更新。
撤销选择体现了回溯的根本理念。为了找到所有符合情况的path，需要对决策阶段做出的决策进行撤销，以防止影响到下一个选择的决策。
回溯一般是组合问题看到组合问题优先考虑回溯。
全排列
回溯要理解先进后出的思想，全排列问题是一个经典的回溯问题。全排列问题是给定一个不重复的数组，返回这个数组的全排列。这个问题的解题思路是，每次从数组中选择一个数字，然后递归的求剩下的数字的全排列。这里的选择就是决策，需要选择那些没有被使用的数字，所以还需要一个record数组，撤销选择就是将选择的数字放回数组中。结束递归条件就是path的长度等于数组的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
vector<vector<int>> ans;
vector<int> path;
void dfs(vector<int>& nums, vector<int>& record) {
if (path.size() == nums.size()) {
ans.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
// 选择没有被使用过的
if (record[i] == 0) {
path.push_back(nums[i]);
record[i] = 1;
dfs(nums, record);
path.pop_back();
record[i] = 0;
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<int> record(nums.size(), 0); // 先大小再元素值
dfs(nums, record);
return ans;
}
子集
选择一个数字，然后递归的求解后面的数的子集。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<vector<int>> ans = {};
void dfs(vector<int>& nums, int i, vector<int>& cur) {
if(i == nums.size()) return;
for(int j = i; j < nums.size(); j++) {
cur.push_back(nums[j]);
dfs(nums, j + 1, cur);
ans.push_back(cur);
cur.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<int> cur;
ans.push_back({});
dfs(nums, 0, cur);
return ans;
}
组合
子集的特例，就是规定了子集的长度。
组合求和
电话号码的字母组合
每一选一个digit，遍历所有的字母，循环内添加一个字母（决策）后进行迭代，在path长度等于digits长度时结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<string> ans;
vector<string> letterMap = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
void dfs(string& digits, int i, string& path) {
if(i == digits.size()) {
ans.push_back(path);
return;
}
for(auto c : letterMap[digits[i] - '2']) {
path.push_back(c);
dfs(digits, i + 1, path);
path.pop_back();
}
}
vector<string> letterCombinations(string digits) {
if(digits.empty()) return {};
string path;
dfs(digits, 0, path);
return ans;
}
组合总和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> state; // 状态（子集）
sort(candidates.begin(), candidates.end()); // 对 candidates 进行排序
int start = 0; // 遍历起始点
vector<vector<int>> res; // 结果列表（子集列表）
backtrack(state, target, candidates, start, res);
return res;
}
private:
void backtrack(vector<int> &state, int target, vector<int> &choices, int start, vector<vector<int>> &res) {
// 子集和等于 target 时，记录解
if (target == 0) {
res.push_back(state);
return;
}
// 遍历所有选择
// 剪枝二：从 start 开始遍历，避免生成重复子集
for (int i = start; i < choices.size(); i++) {
// 剪枝一：若子集和超过 target ，则直接结束循环
// 这是因为数组已排序，后边元素更大，子集和一定超过 target
if (target - choices[i] < 0) {
break;
}
// 尝试：做出选择，更新 target, start
state.push_back(choices[i]);
// 进行下一轮选择
backtrack(state, target - choices[i], choices, i, res);
// 回退：撤销选择，恢复到之前的状态
state.pop_back();
}
}
};
括号生成
核心：右括号的数量要始终小于左括号的数量。左括号的数量不能大于n。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# 找单词
图的深度遍历
```cpp
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int rows = board.size(), cols = board[0].size();
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (board[r][c] == word[0] && dfs(board, word, 0, r, c)) {
return true;
}
}
}
return false;
}
bool dfs(vector<vector<char>>& board, string& word, int index, int row, int col) {
if (index == word.size()) {
return true;
}
if (row < 0 || col < 0 || row >= board.size() || col >= board[0].size()) {
return false;
}
if (board[row][col] != word[index]) {
return false;
}
auto board_val = board[row][col];
board[row][col] = '0';
bool result = dfs(board, word, index + 1, row - 1, col);
result = result || dfs(board, word, index + 1, row + 1, col);
result = result || dfs(board, word, index + 1, row, col - 1);
result = result || dfs(board, word, index + 1, row, col + 1);
board[row][col] = board_val;
return result;
}
};
分割回文串
在回溯获得子集的过程中，用双指针判断子集是否是回文串。需要注意只有在递归结束时再把path加入到res中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
vector<string> path;
dfs(s, 0, path, res);
return res;
}
void dfs(string& s, int start, vector<string>& path, vector<vector<string>>& res) {
if (start == s.size()) {
res.push_back(path);
return;
}
for (int i = start; i < s.size(); i++) {
if (isPalindrome(s, start, i)) {
path.push_back(s.substr(start, i - start + 1));
dfs(s, i + 1, path, res);
path.pop_back();
}
}
}
bool isPalindrome(string& s, int start, int end) {
while (start < end) {
if (s[start] != s[end]) {
return false;
}
start++;
end--;
}
return true;
}
};
This post is licensed under CC BY 4.0 by the author.