【数据结构与算法】 LeetCode：回溯
文章目录
- 回溯算法
- 组合
- 组合总和（Hot 100）
- 组合总和 II
- 电话号码的字母组合（Hot 100）
- 括号生成（Hot 100）
- 分割回文串（Hot 100）
- 复原IP地址
- 子集（Hot 100）
- 全排列（Hot 100）
- N皇后（Hot 100）
- 单词搜索（Hot 100）
回溯算法
组合
组合
class Solution {
private:
vector<vector<int>> result; // 存放符合条件结果的集合
vector<int> path; // 用来存放符合条件结果
void backtracking(int n, int k, int startIndex) {
if (path.size() == k) {
result.push_back(path);
return;
}
for (int i = startIndex; i <= n; i++) {
path.push_back(i); // 处理节点
backtracking(n, k, i + 1); // 递归
path.pop_back(); // 回溯，撤销处理的节点
}
}
public:
vector<vector<int>> combine(int n, int k) {
backtracking(n, k, 1);
return result;
}
};
剪枝。例如，去掉达不到k=4的分支：
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(int n, int k, int startIndex) {
if (path.size() == k) {
result.push_back(path);
return;
}
// 剪枝优化
// 还需要的元素个数为: k - path.size();
// 令待加入path的数为：i = startIndex；i及其之后的元素个数:n - i +1
// 需要满足：k - path.size() <= n - i +1
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
path.push_back(i); // 处理节点
backtracking(n, k, i + 1);
path.pop_back(); // 回溯，撤销处理的节点
}
}
public:
vector<vector<int>> combine(int n, int k) {
backtracking(n, k, 1);
return result;
}
};
组合总和（Hot 100）
组合总和
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
if (sum > target) {
return;
}
if (sum == target) {
result.push_back(path);
return;
}
for (int i = startIndex; i < candidates.size(); i++) {
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum, i); // 不用i+1了，表示可以重复读取当前的数
sum -= candidates[i];
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
result.clear();
path.clear();
backtracking(candidates, target, 0, 0);
return result;
}
};
组合总和 II
组合总和 II
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
if (sum > target) {
return;
}
if (sum == target) {
result.push_back(path);
return;
}
for (int i = startIndex; i < candidates.size(); i++) {
// 避免同一层级重复使用相同的元素
if (i > startIndex && candidates[i] == candidates[i - 1]) {
continue;
}
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum, i + 1); // 注意这里是 i + 1，表示下一层级不再使用当前元素
sum -= candidates[i];
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end()); // 首先对候选数组进行排序，以便处理重复元素的情况
backtracking(candidates, target, 0, 0);
return result;
}
};
电话号码的字母组合（Hot 100）
电话号码的字母组合
class Solution {
private:
const string letterMap[10] = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz", // 9
};
public:
vector<string> result;
string s;
void backtracking(const string& digits, int index) {
if (index == digits.size()) {
result.push_back(s);
return;
}
int digit = digits[index] - '0'; // 将index指向的数字转为int
string letters = letterMap[digit]; // 取数字对应的字符集
for (int i = 0; i < letters.size(); i++) {
s.push_back(letters[i]); // 处理
backtracking(digits, index + 1); // 递归，注意index+1，下一层要处理下一个数字了
s.pop_back(); // 回溯
}
}
vector<string> letterCombinations(string digits) {
s.clear();
result.clear();
if (digits.size() == 0) return result;
backtracking(digits, 0);
return result;
}
};
括号生成（Hot 100）
括号生成
左括号 ‘(’ 必须用相同数量的右括号 ‘)’ 闭合。
左括号 ‘(’ 必须在对应的右括号 ‘)’ 之前。
class Solution {
void backtrack(vector<string>& ans, // 存储结果的vector
string& cur, // 当前生成的括号组合字符串
int open, // 当前已经放置的左括号数量
int close, // 当前已经放置的右括号数量
int n) { // 目标括号对的数量
// 如果当前括号组合的长度达到了目标长度（即2n）
if (cur.size() == n * 2) {
// 将当前组合添加到结果中
ans.push_back(cur);
// 回溯完成，返回上一层
return;
}
// 如果左括号数量小于n，说明可以继续放置左括号
if (open < n) {
// 在当前组合后添加一个左括号
cur.push_back('(');
// 递归调用，左括号数量加1，右括号数量不变
backtrack(ans, cur, open + 1, close, n);
// 回溯，撤销刚才的选择（即移除刚才添加的左括号）
cur.pop_back();
}
// 如果右括号数量小于左括号数量，说明可以继续放置右括号
if (close < open) {
// 在当前组合后添加一个右括号
cur.push_back(')');
// 递归调用，左括号数量不变，右括号数量加1
backtrack(ans, cur, open, close + 1, n);
// 回溯，撤销刚才的选择（即移除刚才添加的右括号）
cur.pop_back();
}
}
public:
vector<string> generateParenthesis(int n) {
vector<string> ans; // 存储最终结果的vector
string current; // 当前正在构建的括号组合
// 回溯生成括号组合
backtrack(ans, current, 0, 0, n);
return ans;
}
};
分割回文串（Hot 100）
分割回文串
class Solution {
private:
vector<vector<string>> result; // [ ["aa","b"], ["a","a","b"] ]
vector<string> path; // 放已经回文的子串 ["aa","b"]或 ["a","a","b"]
void backtracking (const string& s, int startIndex) {
// 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
if (startIndex >= s.size()) {
result.push_back(path);
return;
}
for (int i = startIndex; i < s.size(); i++) {
// 存在不是回文的字串,跳过之后的递归(因为分割得到的所有子串都必须为回文的)
if (!isPalindrome(s, startIndex, i)) continue;
// 与组合不同，这里是分割
// 获取[startIndex,i]在s中的子串
string str = s.substr(startIndex, i - startIndex + 1);
path.push_back(str);
backtracking(s, i + 1); // 寻找i+1为起始位置的子串
path.pop_back(); // 回溯过程，弹出本次已经添加的子串
}
}
bool isPalindrome(const string& s, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
if (s[i] != s[j]) return false;
}
return true;
}
public:
vector<vector<string>> partition(string s) {
result.clear();
path.clear();
backtracking(s, 0);
return result;
}
};
复原IP地址
复原IP地址
// https://www.programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html#%E6%80%9D%E8%B7%AF
class Solution {
private:
vector<string> result;// 记录结果
// startIndex: 搜索的起始位置，pointNum:添加逗点的数量
void backtracking(string& s, int startIndex, int pointNum) {
if (pointNum == 3) { // 逗点数量为3时，分隔结束
// 判断第四段子字符串是否合法，如果合法就放进result中
if (isValid(s, startIndex, s.size() - 1)) {
result.push_back(s);
}
return;
}
for (int i = startIndex; i < s.size(); i++) {
if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法
s.insert(s.begin() + i + 1 , '.'); // 在i的后面插入一个逗点
pointNum++;
backtracking(s, i + 2, pointNum); // 插入逗点之后下一个子串的起始位置为i+2
pointNum--; // 回溯
s.erase(s.begin() + i + 1); // 回溯删掉逗点
} else break; // 不合法，直接结束本层循环
}
}
// 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
bool isValid(const string& s, int start, int end) {
if (start > end) {
return false;
}
if (s[start] == '0' && start != end) { // 0开头的数字不合法
return false;
}
int num = 0;
for (int i = start; i <= end; i++) {
if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
return false;
}
num = num * 10 + (s[i] - '0');
if (num > 255) { // 如果大于255了不合法
return false;
}
}
return true;
}
public:
vector<string> restoreIpAddresses(string s) {
result.clear();
if (s.size() < 4 || s.size() > 12) return result; // 算是剪枝了
backtracking(s, 0, 0);
return result;
}
};
子集（Hot 100）
子集
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex) {
result.push_back(path); // 收集子集
for (int i = startIndex; i < nums.size(); i++) {
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
backtracking(nums, 0);
return result;
}
};
全排列（Hot 100）
全排列
class Solution {
private:
void backtrack(vector<int>& nums, vector<vector<int>>& result, int start){
if(start == nums.size()-1 ){
result.push_back(nums);
return;
}
for(int i = start; i < nums.size(); i++){
swap(nums[i],nums[start]);
backtrack(nums, result,start+1);
swap(nums[i],nums[start]);
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
backtrack(nums, result, 0);
return result;
}
};
N皇后（Hot 100）
N皇后
class Solution {
private:
vector<vector<string>> result;
void backtracking(int n, int row, vector<string>& chessboard) {
if (row == n) {
result.push_back(chessboard);
return;
}
for (int col = 0; col < n; col++) {
// 递归的时候row + 1，每一行放一个，所以不用对行进行检查
if (isValid(row, col, chessboard, n)) { // 验证合法就可以放
chessboard[row][col] = 'Q'; // 放置皇后
backtracking(n, row + 1, chessboard);
chessboard[row][col] = '.'; // 回溯，撤销皇后
}
}
}
bool isValid(int row, int col, vector<string>& chessboard, int n) {
// 检查列
for (int i = 0; i < row; i++) { // 这是一个剪枝
if (chessboard[i][col] == 'Q') return false;
}
// 检查 45度角是否有皇后
for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
if (chessboard[i][j] == 'Q') return false;
}
// 检查 135度角是否有皇后
for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (chessboard[i][j] == 'Q') return false;
}
return true;
}
public:
vector<vector<string>> solveNQueens(int n) {
result.clear();
std::vector<std::string> chessboard(n, std::string(n, '.'));
backtracking(n, 0, chessboard);
return result;
}
};
单词搜索（Hot 100）
单词搜索
class Solution {
private:
int rows, cols;
bool dfs(vector<vector<char>>& board, string word, int i, int j, int k) {
// k 表示在 word 字符串中当前要匹配的字符的索引
// i越界或j越界或不匹配
if (i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] != word[k]) return false;
// board[i][j] = word[k]
if (k == word.size() - 1) return true; // 字符串匹配完成
board[i][j] = '\0'; // 代表此元素已访问过，防止之后搜索时重复访问
// 搜索下一单元格： 朝当前元素的 上、下、左、右 四个方向开启下层递归，
// 使用或代表只需找到一条可行路径就直接返回，不再做后续 DFS，并记录结果至 res
bool res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
board[i][j] = word[k]; // 回溯：还原当前矩阵元素
return res;
}
public:
bool exist(vector<vector<char>>& board, string word) {
rows = board.size();
cols = board[0].size();
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) { // 每一个格子向四周
if (dfs(board, word, i, j, 0)) return true;
}
}
return false;
}
};