LeetCode Hot 100：回溯
46. 全排列
class Solution {
private:
vector<vector<int>> ans;
public:
vector<vector<int>> permute(vector<int>& nums) {
if (nums.empty())
return {};
backtrace(nums, 0, (int)nums.size());
return ans;
}
void backtrace(vector<int>& path, int level, int n) {
if (level == n) {
ans.push_back(path);
return;
}
for (int i = level; i < n; i++) {
swap(path[i], path[level]);
backtrace(path, level + 1, n);
swap(path[i], path[level]);
}
}
};
78. 子集
class Solution {
private:
vector<vector<int>> ans;
public:
vector<vector<int>> subsets(vector<int>& nums) {
if (nums.empty())
return {};
vector<int> path;
backtrace(nums, 0, (int)nums.size(), path);
return ans;
}
void backtrace(vector<int>& nums, int level, int n, vector<int> path) {
if (level == n) {
ans.push_back(path);
return;
}
path.push_back(nums[level]);
backtrace(nums, level + 1, n, path);
path.pop_back();
backtrace(nums, level + 1, n, path);
}
};
17. 电话号码的字母组合
class Solution {
private:
unordered_map<char, string> dict{
{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
{'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};
vector<string> ans;
public:
vector<string> letterCombinations(string digits) {
if (digits.empty())
return {};
int n = digits.length();
string path;
backtrace(digits, 0, n, path);
return ans;
}
void backtrace(string& digits, int level, int n, string path) {
if (level == n) {
ans.push_back(path);
return;
}
char digit = digits[level];
string s = dict[digit];
for (char& c : s) {
path.push_back(c);
backtrace(digits, level + 1, n, path);
path.pop_back();
}
}
};
39. 组合总和
class Solution {
private:
vector<vector<int>> ans;
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
if (candidates.empty())
return {};
int n = candidates.size();
vector<int> path;
backtrace(candidates, 0, n, target, path);
return ans;
}
void backtrace(vector<int>& nums, int level, int n, int target,
vector<int> path) {
if (level == n)
return;
if (accumulate(path.begin(), path.end(), 0) == target) {
ans.push_back(path);
return;
}
// 选 nums[level]
if (accumulate(path.begin(), path.end(), 0) + nums[level] <= target) {
path.push_back(nums[level]);
backtrace(nums, level, n, target, path);
path.pop_back();
}
// 不选 nums[level]
backtrace(nums, level + 1, n, target, path);
}
};
22. 括号生成
思路 1：回溯
class Solution {
private:
vector<string> ans;
public:
vector<string> generateParenthesis(int n) {
if (n == 0)
return {};
string path;
backtrace(0, 2 * n, path);
return ans;
}
void backtrace(int level, int n, string path) {
if (level == n) {
if (isValid(path))
ans.push_back(path);
return;
}
path.push_back('(');
backtrace(level + 1, n, path);
path.pop_back();
path.push_back(')');
backtrace(level + 1, n, path);
path.pop_back();
}
// 辅函数 - 判断字符串 s 是否有效
bool isValid(const string& s) {
int balance = 0;
for (const char& c : s) {
if (c == '(')
balance++;
else
balance--;
if (balance < 0)
return false;
}
return balance == 0;
}
};
思路 2：深度优先搜索
class Solution {
private:
vector<string> ans;
public:
vector<string> generateParenthesis(int n) {
if (n == 0)
return {};
function<void(int, int, string)> dfs = [&](int left, int right, string str) {
if (left < 0 || right < 0 || left > right)
return;
if (left == 0 && right == 0) {
ans.push_back(str);
return;
}
dfs(left - 1, right, str + '(');
dfs(left, right - 1, str + ')');
};
dfs(n, n, "");
return ans;
}
};
79. 单词搜索
/*
* @lc app=leetcode.cn id=79 lang=cpp
*
* [79] 单词搜索
*/
// @lc code=start
class Solution {
private:
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
public:
// 主函数
bool exist(vector<vector<char>>& board, string word) {
if (board.empty())
return false;
int m = board.size(), n = m ? board[0].size() : 0;
vector<vector<bool>> visited(m, vector<bool>(n, false));
bool find = false;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
backtrack(i, j, 0, board, word, find, visited);
return find;
}
// 辅函数（注意传引用，否则TLE）
void backtrack(int i, int j, int level, vector<vector<char>>& board,
string& word, bool& find, vector<vector<bool>>& visited) {
if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size())
return;
if (visited[i][j] || find || board[i][j] != word[level])
return;
if (level == word.size() - 1) {
find = true;
return;
}
visited[i][j] = true; // 修改当前节点状态
// 递归子节点
for (int k = 0; k < 4; k++) {
int r = i + dx[k];
int c = j + dy[k];
backtrack(r, c, level + 1, board, word, find, visited);
}
visited[i][j] = false; // 回改当前节点状态
}
};
// @lc code=end
131. 分割回文串
/*
* @lc app=leetcode.cn id=131 lang=cpp
*
* [131] 分割回文串
*/
// @lc code=start
// 回溯
class Solution {
private:
vector<vector<string>> ans;
public:
vector<vector<string>> partition(string s) {
int n = s.length();
vector<string> path;
backtrack(s, 0, n, 0, path);
return ans;
}
void backtrack(string s, int level, int n, int start, vector<string> path) {
if (level == n) {
ans.push_back(path);
return;
}
if (level < n - 1) {
// 跳过当前字符 s[level]
backtrack(s, level + 1, n, start, path);
}
if (isPalindrome(s, start, level)) {
// s[start, level] 是一个回文串
string tmp = s.substr(start, level - start + 1);
path.push_back(tmp);
// 下一个回文串从 level+1 开始
backtrack(s, level + 1, n, level + 1, path);
// 回溯
path.pop_back();
}
}
// 辅函数 - 判断字符串 s 的 [left, right] 部分是否回文
bool isPalindrome(const string& s, int left, int right) {
while (left < right) {
if (s[left] != s[right])
return false;
left++;
right--;
}
return true;
}
};
// @lc code=end
51. N 皇后
class Solution {
private:
vector<vector<string>> ans;
public:
vector<vector<string>> solveNQueens(int n) {
if (n == 0)
return {};
// 初始化棋局
vector<string> board(n, string(n, '.'));
// 每行每行放置皇后
backtrack(board, 0, n);
return ans;
}
void backtrack(vector<string> board, int row, int n) {
if (row == n) {
ans.push_back(board);
return;
}
for (int col = 0; col < n; col++) {
if (check(board, row, col, n) == false)
continue;
board[row][col] = 'Q';
backtrack(board, row + 1, n);
board[row][col] = '.';
}
}
bool check(const vector<string>& board, int row, int col, int n) {
// 同一列
for (int i = 0; i < row; i++)
if (board[i][col] == 'Q')
return false;
// 斜上方
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i]