【数据结构与算法】 LeetCode：回溯

回溯算法

组合

组合

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 +1for (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指向的数字转为intstring 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+2pointNum--;                         // 回溯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;}
};