LeetCode刷题记录（回溯篇）
LeetCode刷题记录（回溯篇），个人向。
[46] Permutations
难度：Medium
语言：C++
题目描述。
使用used来记录当前已使用的元素，尝试增加used，递归调用，记录path，在path长度达到nums.size()时将结果记录到result即可。
class Solution {
public:
void backtracking(vector<int> &nums, vector<bool> &used, vector<int> &path,
vector<vector<int>> &result) {
int size = nums.size();
if (path.size() == size) {
result.push_back(path);
return;
}
for (int i = 0; i < size; ++i) {
if (used[i]) {
continue;
}
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, used, path, result);
path.pop_back();
used[i] = false;
}
return;
}
vector<vector<int>> permute(vector<int> &nums) {
vector<bool> used(nums.size(), false);
vector<int> path;
vector<vector<int>> result;
backtracking(nums, used, path, result);
return result;
}
};
[78] Subsets
难度：Medium
语言：C++
题目描述。
相比上一题求全排列，这一题的不同点有二：
- 我们要求的是子集，单个集合不要求包含所有元素，因此在这棵递归树上，我们要求的不止是叶子节点，而是所有节点。因此不是在递归结束的时候记录结果，而是每次调用都记录一下结果。
- 相比全排列，集合对元素的顺序不再做要求。因此相比之前使用
used数组，这里可以只记录startIndex，然后每次递归从startIndex往后遍历，来做到包含不同的元素组合。
class Solution {
public:
void backtracking(vector<int> &nums, int startIndex, vector<int> &path,
vector<vector<int>> &result) {
int size = nums.size();
result.push_back(path);
for (int i = startIndex; i < size; ++i) {
path.push_back(nums[i]);
backtracking(nums, i + 1, path, result);
path.pop_back();
}
}
vector<vector<int>> subsets(vector<int> &nums) {
vector<int> path;
vector<vector<int>> result;
backtracking(nums, 0, path, result);
return result;
}
};
[17] Letter Combinations of a Phone Number
难度：Medium
语言：C++
题目描述。
构造一个mapping用来存数字到字母的映射，同时用mapping[digits[startIndex] - '2']来取这个映射。回溯部分和之前大同小异，更新一下startIndex，同时记录路径，最后加进result即可。
class Solution {
public:
const vector<string> mapping = {"abc", "def", "ghi", "jkl",
"mno", "pqrs", "tuv", "wxyz"};
void backtracking(string &digits, int startIndex, string &path,
vector<string> &result) {
int size = digits.size();
if (startIndex >= size) {
if (size > 0) {
result.push_back(path);
}
return;
}
string chars = mapping[digits[startIndex] - '2'];
int numChars = chars.size();
for (int i = 0; i < numChars; ++i) {
path.push_back(chars[i]);
backtracking(digits, startIndex + 1, path, result);
path.pop_back();
}
}
vector<string> letterCombinations(string digits) {
vector<string> result;
string path;
backtracking(digits, 0, path, result);
return result;
}
};
[39] Combination Sum
难度：Medium
语言：C++
题目描述。
对回溯的代码逐渐熟练，同样是一次写出答案。
和之前的代码大同小异。这里因为candidates[i]是大于0的，所以出现new_sum == target就不用继续递归了。
当我们选择了某个数字，则以后的递归只会考虑该数字以及之后的数字，不再考虑之前的数字，这保证了结果的唯一性（不出现重复组合）。
这道题的关键在于数字是可以重复使用的，这里我们用递归参数所使用的index为i而不是i+1来体现。
class Solution {
public:
void backtracking(const vector<int> &candidates, const int target,
int index, int cur_sum, vector<int> &choosen,
vector<vector<int>> &result) {
int size = candidates.size();
if (index >= size) {
return;
}
for (int i = index; i < size; ++i) {
int new_sum = cur_sum + candidates[i];
if (new_sum > target) {
continue;
}
choosen.push_back(candidates[i]);
if (new_sum == target) {
result.push_back(choosen);
// 0 will not appear in candidates, and 2 <= candidates[i] <= 40
// so no need to backtrack further
} else {
backtracking(candidates, target, i, new_sum, choosen, result);
}
choosen.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
vector<int> choosen;
vector<vector<int>> result;
backtracking(candidates, target, 0, 0, choosen, result);
return result;
}
};
[22] Generate Parentheses
难度：Medium
语言：C++
题目描述。
回溯时同时记录左括号和右括号的剩余数量。若左括号剩余数量大于0则可以添加左括号。若右括号剩余数量大于左括号（防止先右括号后左括号导致无法匹配）则可以添加右括号。
class Solution {
public:
void backtracking(int left, int right, string &s, vector<string> &result) {
if (left == 0 && right == 0) {
result.push_back(s);
return;
}
if (left > 0) {
s.push_back('(');
backtracking(left - 1, right, s, result);
s.pop_back();
}
if (right > left) {
s.push_back(')');
backtracking(left, right - 1, s, result);
s.pop_back();
}
}
vector<string> generateParenthesis(int n) {
string s;
vector<string> result;
backtracking(n, n, s, result);
return result;
}
};
[79] Word Search
难度：Medium
语言：C++
题目描述。
代码有些类似DFS。记录当前坐标x和y以及要匹配的字符的index k。如果当前字符不对则递归终止，否则看k是否已经到word的最后一个了，如果没有就通过DFS的方式去搜索周围四个。
class Solution {
public:
vector<pair<int, int>> directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
bool backtracking(const vector<vector<char>> &board, const string &word,
int x, int y, int k, vector<vector<bool>> &visited) {
if (board[x][y] != word[k]) {
return false;
} else if (k == word.size() - 1) {
return true;
}
int m = board.size();
int n = board[0].size();
visited[x][y] = true;
for (auto [dx, dy] : directions) {
int nx = x + dx, ny = y + dy;
if (nx < 0 || ny < 0 || nx >= m || ny >= n || visited[nx][ny]) {
continue;
}
if (backtracking(board, word, nx, ny, k + 1, visited)) {
return true;
}
}
visited[x][y] = false;
return false;
}
bool exist(vector<vector<char>> &board, string word) {
int m = board.size();
int n = board[0].size();
vector<vector<bool>> visited(board.size(),
vector<bool>(board[0].size(), false));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (backtracking(board, word, i, j, 0, visited)) {
return true;
}
}
}
return false;
}
};
[131] Palindrome Partitioning
难度：Medium
语言：C++
题目描述。
还是回溯题的老套路。记录一下startIndex，然后for循环从startIndex开始找下一个回文子串。若startIndex到i是回文子串，则记录到path，然后从i+1递归即可。
至于判断是否是回文串，这里写了两个版本。一种是常规使用双指针来判断字符串是否是回文串（isPalindrome）；另一种是优化方法，使用了动态规划做预处理，提前算好所有子串是否是回文串（palindromeTable），判断的时候直接查表即可，避免了重复计算。
class Solution {
vector<vector<bool>> palindromeTable;
bool isPalindrome(const string &s, int startIndex, int endIndex) {
while (startIndex <= endIndex) {
if (s[startIndex] != s[endIndex]) {
return false;
}
++startIndex;
--endIndex;
}
return true;
}
void backtracking(const string &s, int startIndex, vector<string> &path,
vector<vector<string>> &result) {
int size = s.size();
if (startIndex >= size) {
result.push_back(path);
return;
}
for (int i = startIndex; i < size; ++i) {
// if (isPalindrome(s, startIndex, i)) {
if (palindromeTable[startIndex][i]) {
path.push_back(s.substr(startIndex, i - startIndex + 1));
backtracking(s, i + 1, path, result);
path.pop_back();
}
}
}
public:
vector<vector<string>> partition(string s) {
vector<string> path;
vector<vector<string>> result;
int size = s.size();
palindromeTable.assign(size, vector<bool>(size, true));
for (int i = size - 1; i >= 0; --i) {
for (int j = i + 1; j < size; ++j) {
palindromeTable[i][j] =
palindromeTable[i + 1][j - 1] && s[i] == s[j];
}
}
backtracking(s, 0, path, result);
return result;
}
};
[51] N-Queens
难度：Hard
语言：C++
题目描述。
大名鼎鼎的N皇后问题。看似暴力穷举的背后又存在许多可剪枝优化的空间。
- 每轮递归无需两个坐标轴双重循环遍历。我们可规定递归的顺序是从最上面一行到最下面一行，每次在一行里面找下一个N皇后的位置。这样一方面保证了顺序（防止出现重复结果），另一方面我们实际只需要一层循环，即遍历这一行的位置，看哪一列可作为N皇后的位置即可。如果找到位置，再递归进入下一行的遍历查找。
- 检查位置是否合法时，由于我们填N皇后的位置是从上到下（按行）来填的，因此我们只需要检查行坐标小于当前坐标的那些位置即可，可减少检查判断的数量。（要注意皇后除了横着竖着还能斜着走，一开始不了解规则都没注意这个）
当我们最后填完了最后一行（n == row），说明每一行我们都已经找到了一个合法的N皇后的位置，将此时的棋盘加入结果即可（result.push_back(board);）。
class Solution {
bool check(int n, int x, int y, const vector<string> &board) {
for (int i = 0; i < x; ++i) {
if (board[i][y] == 'Q') {
return false;
}
}
const vector<pair<int, int>> direction = {{-1, 1}, {-1, -1}};
for (int i = 1; i < n; ++i) {
for (auto [dx, dy] : direction) {
int nx = x + i * dx;
int ny = y + i * dy;
if (nx < 0 || ny < 0 || ny >= n) {
continue;
}
if (board[nx][ny] == 'Q') {
return false;
}
}
}
return true;
}
void backtracking(int n, int row, vector<string> &board,
vector<vector<string>> &result) {
if (n == row) {
result.push_back(board);
return;
}
for (int j = 0; j < n; ++j) {
if (check(n, row, j, board)) {
board[row][j] = 'Q';
backtracking(n, row + 1, board, result);
board[row][j] = '.';
}
}
}
public:
vector<vector<string>> solveNQueens(int n) {
vector<string> board(n, string(n, '.'));
vector<vector<string>> result;
backtracking(n, 0, board, result);
return result;
}
};
总结
回溯的题目基本都存在一套函数模版：
void backtracking(parameters) {
if (termination_condition) {
store_result;
return;
}
for (choice : elements in the current level's set (the number of children of a tree node is the size of the set)) {
process_node;
backtracking(path, choices); // recursive call
backtrack, undo processing result
}
}
这里的几道题目的代码基本都是按着上面的模版来的，无非有一些小修改。除了[22] Generate Parentheses在递归上略为特殊，其记录了剩余左括号和右括号的数量，然后再根据该数量关系来决定如何递归。