LeetCode 热题 100 | 回溯（二）

目录

1  39. 组合总和

2  22. 括号生成

3  79. 单词搜索

---

菜鸟做题，语言是 C++，感冒快好版

关于对回溯算法的理解请参照我的上一篇博客；

在之后的博客中，我将只分析回溯算法中的 for 循环。

1  39. 组合总和

题眼：candidates 中的同一个数字可以无限制重复被选取。

根据题眼，for 循环结构如下：

for (int i = begin; i < candidates.size(); ++i) {output.push_back(candidates[i]);sum += candidates[i];helper(candidates, target, output, i, sum);sum -= candidates[i];output.pop_back();
}

与之前题解的唯一不同之处在于：递归时传的不再是 begin + 1，而是 i 。这是由于每个字母都可以被重复使用，因此我们可以从当前字母开始选择，而非跳过它。

思路说明图：

假设 target = 8 。在第一层函数中，i = begin = 0，即从 2 开始选择，再将 i 传给第二层函数；在第二层函数中，i = begin = 0，即从 2 开始选择，再将 i 传给第三层函数；以此类推。直到第五层函数，此时 sum = 2 + 2 + 2 + 2 > 8，即继续加下去也永远无法得到 target 。因此，返回到第四层函数，i += 1，即考虑 3 是否可行。以此类推。

由上述分析可得，递归终止条件为：

if (sum > target) return;
if (sum == target) {ans.push_back(output);return;
}

一是，当前 sum 已经大于 target，不能再增加下去了；二是，当前 sum 已经等于 target，也不能再增加下去了（区别在于，我们要将成功的组合记录下来）。

class Solution {
public:vector<vector<int>> ans;void helper(vector<int> & candidates, int target,vector<int> & output, int begin, int sum) {if (sum > target) return;if (sum == target) {ans.push_back(output);return;}for (int i = begin; i < candidates.size(); ++i) {output.push_back(candidates[i]);sum += candidates[i];helper(candidates, target, output, i, sum);sum -= candidates[i];output.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<int> output;helper(candidates, target, output, 0, 0);return ans;}
};

你可能会认为传递的参数太多，那你可以把它们都定义成全局变量。

2  22. 括号生成

for 循环结构如下：

output.push_back('(');
++l;
helper(output, n, l, r);
output.pop_back();
--l;
output.push_back(')');
++r;
helper(output, n, l, r);
output.pop_back();
--r;

这种写法和  78. 子集  很像。在  78. 子集  中，只有两种选择，即是否让当前字母进入子集；同样地，在本题中也只有两种选择，即当前坑位填左括号还是右括号（我们还设置了变量来记录当前左右括号的个数）。

递归终止条件为：

if (l > n || r > n || r > l) return;
if (l == n && r == n) {ans.push_back(output);return;
}

一是，如果当前左或右括号的个数大于所需的个数，则返回；二是，如果当前右括号的个数大于当前左括号的个数，则返回，这是因为该右括号肯定找不到配对的左括号；三是，如果左右括号的个数都等于所需的个数了，则记录成功的组合并返回。

class Solution {
public:vector<string> ans;void helper(string & output, int n, int l, int r) {if (l > n || r > n || r > l) return;if (l == n && r == n) {ans.push_back(output);return;}output.push_back('(');++l;helper(output, n, l, r);output.pop_back();--l;output.push_back(')');++r;helper(output, n, l, r);output.pop_back();--r;}vector<string> generateParenthesis(int n) {string output;helper(output, n, 0, 0);return ans;}
};

3  79. 单词搜索

非典型 for 循环结构如下：

visited[r][c] = 1;bool up = false, down = false, left = false, right = false;
if (r - 1 >= 0 && !visited[r - 1][c]) left = helper(board, word, r - 1, c, i + 1);
if (r + 1 < nr && !visited[r + 1][c]) right = helper(board, word, r + 1, c, i + 1);
if (c - 1 >= 0 && !visited[r][c - 1]) up = helper(board, word, r, c - 1, i + 1);
if (c + 1 < nc && !visited[r][c + 1]) down = helper(board, word, r, c + 1, i + 1);visited[r][c] = 0;return up || down || left || right;

这里的 “选择” 就是 “从当前位置出发，有四个方向可以走”。本来想写个 for 循环来遍历四个方向的，无奈这里有返回值，因此无法一概而论。这里的结构还是满足 “处理-递归-清除” 的格式，只是最后多了一个返回值。只要有一个方向能走得通，我们都返回 true 。

它不像之前的题一样，每个坑位/位置管好自己即可，而是要和后面的坑位/位置共荣辱。

递归终止条件：

if (board[r][c] != word[i]) return false;
if (i == word.size() - 1) return true;

一是，当前字母与 word 中的字母不同，返回 false；二是，已经找到了所有字母，返回 true 。

这道题感觉像是图论和回溯的杂合体啊啊啊。之前的题都是只有一个方向（右），而这道题有四个方向（上下左右）。

class Solution {
public:int nr, nc;vector<vector<int>> visited;bool helper(vector<vector<char>> & board, string word, int r, int c, int i) {if (board[r][c] != word[i]) return false;if (i == word.size() - 1) return true;visited[r][c] = 1;bool up = false, down = false, left = false, right = false;if (r - 1 >= 0 && !visited[r - 1][c])left = helper(board, word, r - 1, c, i + 1);if (r + 1 < nr && !visited[r + 1][c])right = helper(board, word, r + 1, c, i + 1);if (c - 1 >= 0 && !visited[r][c - 1])up = helper(board, word, r, c - 1, i + 1);if (c + 1 < nc && !visited[r][c + 1])down = helper(board, word, r, c + 1, i + 1);visited[r][c] = 0;return up || down || left || right;}bool exist(vector<vector<char>>& board, string word) {nr = board.size();nc = board[0].size();visited.resize(nr);for (auto & v : visited)v.resize(nc);for (int i = 0; i < nr; ++i) {for (int j = 0; j < nc; ++j) {if (helper(board, word, i, j, 0)) return true;}}return false;}
};

说明：我们认为每个位置都有可能是 word 的起始点，因此使用双重 for 循环进行遍历。不过，只有当找完了 word 时才返回 true；反之，会走向最后的 false 。代码如下：

for (int i = 0; i < nr; ++i) {for (int j = 0; j < nc; ++j) {if (helper(board, word, i, j, 0)) return true;}
}return false;

最好取 row 和 column 的首字母来定义变量，否则把自己都绕晕了。