代码随想录-高级篇之回溯算法

回溯

当你举例子，需要不断用到循环时，这时候就要想到回溯，首先应该举例子，画出树形图，

• 递归函数 + for循环
  

• 回溯方法—纯暴力方法

• 模板

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}

• 回溯三部曲
  • 递归函数返回值
  • 终止条件
  • 单层递归逻辑

组合问题

组合

class Solution {
public:vector<vector<int>> res;vector<int> path;void backtracing(int n, int k,int startIndex){// 终止条件if (path.size() == k){res.push_back(path);return;}//单层递归逻辑for (int i = startIndex; i <= n; i++){path.push_back(i);backtracing(n,k,i+1);//这里是递归逻辑，path.pop_back();}}vector<vector<int>> combine(int n, int k) {// 返回1-n之间，k个说的组合backtracing(n,k,1);return res;}
};

组合总和III

错误版本

/* 找出总和为n的k个数的组合，且这k个数只能是1~9，且每个数只能出现一次*/
class Solution {
public:vector<vector<int>> res;vector<int> path;void backtracing(int n, int k, int startIndex,int curSum){// 终止条件if (path.size() == k && curSum==n)  // 注意这里不能用&&，两个满足其一就应该结束递归了{res.push_back(path);return;}//单层递归逻辑for (int i = startIndex; i <= 9; i++){path.push_back(i);curSum += i;if (curSum <= n){backtracing(n, k, i + 1, curSum);path.pop_back();   // 这里回溯了//curSum  也应该回溯}else {return;}}}//vector<vector<int>> combinationSum3(int k, int n) vector<vector<int>> combinationSum3(int k, int n) {// 找出总和为n的k个数的组合，且这k个数只能是1~9，且每个数只能出现一次backtracing(n, k, 1,0);return res;}
};

正确版本

class Solution {
public:vector<vector<int>> res;vector<int> path;void backtracing(int n, int k, int startIndex, int curSum) {// 终止条件：终止条件有两个，但是这个两个条件不是&&if (path.size() == k) {if (curSum == n) res.push_back(path);return;}// 单层递归逻辑for (int i = startIndex; i <= 9; i++) {path.push_back(i);curSum += i;backtracing(n, k, i + 1, curSum);// 回溯path.pop_back();curSum -= i; // 注意这里也应该回溯}}vector<vector<int>> combinationSum3(int k, int n) {res.clear();path.clear();backtracing(n, k, 1, 0);return res;}
};

求电话号码的字母组合

#include<vector>
#include<iostream>
#include<string>using namespace std;class Solution {
public:string letterMap[10] = {"","","abc","def","ghi","jki","mno","pqrs","tuv","wxyz"};vector<string> res;string path;void backtracing(string digits, int index){if (digits.size() == index)  // 将数字对于的字符串遍历完{res.push_back(path);return;}int number = digits[index] - '0'; // 取出对应的数字，char的数字-‘0’，转为int类型的数字string letter = letterMap[number]; // 取出对应的数字for (int i = 0; i < letter.size(); i++){path.push_back(letter[i]);      backtracing(digits, index + 1); // 递归递归添加下一个数字。path.pop_back();}}// 电话号码的字母组合vector<string> letterCombinations(string digits) {if (digits.size() == 0) {return res;}backtracing(digits, 0);// 返回所有的电话号码的字母组合return res;}
};

组合总和

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracing(vector<int>& candidates, int target, int curSum,int index){if (curSum == target){result.push_back(path);return;}else if (curSum > target)return;for ( ; index < candidates.size();){curSum += candidates[index];path.push_back(candidates[index]);backtracing(candidates, target, curSum,index);path.pop_back();curSum -= candidates[index];index++;}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backtracing(candidates,target,0,0);return result;}
};

标准

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracing(vector<int>& candidates, int target, int curSum,int index){if (curSum == target){result.push_back(path);return;}else if (curSum > target)return;for ( int i = index; index < candidates.size(); i++){curSum += candidates[i];path.push_back(candidates[i]);backtracing(candidates, target, curSum, i);path.pop_back();curSum -= candidates[i];index++;}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backtracing(candidates,target,0,0);return result;}
};

组合总和II

与组合总和III的区别：组合总和III是从1~9中选择，候选数组中本身没有相同的数字，但是组合总和II有相同的数字

结果去重

class Solution {
public:vector<vector<int>> result;vector<int> path;/*思路：想按照组合问题III的走，然后再加入是剔除掉相同的组合即可*/void backtracking(vector<int>& candidates, int target, int curSum, int startIndex) {if (curSum == target) {// 在这里对 path 进行排序并检查是否存在sort(path.begin(), path.end());auto it = find(result.begin(), result.end(), path);// 注意：返回end表示没有找到if (it == result.end()) {  // 如果没有找到相同的 path，则添加到 result 中result.push_back(path);}return;}if (curSum > target)result;for (int i = startIndex; i < candidates.size(); ++i) {path.push_back(candidates[i]);curSum += candidates[i];backtracking(candidates, target, curSum, i + 1);  // 递归调用，传递新的 curSum 和索引path.pop_back();  // 回溯curSum -= candidates[i];}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());  // 对输入数组进行排序backtracking(candidates, target, 0, 0);return result;}
};

过程中去重

class Solution {
public:vector<vector<int>> result;vector<int> path;/*思路：想按照组合问题III的走，然后再加入是剔除掉相同的组合即可*/void backtracking(vector<int>& candidates, int target, int curSum, int startIndex,int used[]) {if (curSum > target)return;if (curSum == target) {result.push_back(path);return;}for (int i = startIndex; i < candidates.size(); ++i) {if (i > 0 && candidates[i - 1] == candidates[i] && used[i - 1] == 0)continue;path.push_back(candidates[i]);used[i] = 1;curSum += candidates[i];backtracking(candidates, target, curSum, i + 1,used);  // 递归调用，传递新的 curSum 和索引path.pop_back();  // 回溯curSum -= candidates[i];used[i] = 0;}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());  // 对输入数组进行排序int* used = new int[candidates.size()];backtracking(candidates, target, 0, 0,used);return result;}
};

切割问题

分割回文串

复原IP地址

直接思路

#include <vector>
#include <string>
using namespace std;class Solution {
public:vector<string> res;string path;int count = 0;vector<string> restoreIpAddresses(string s) {backtracking(s, 0);return res;}private:void backtracking(const string& s, int start) {// 如果已经找到了4段(IP地址应该由4段组成)，并且遍历完了整个字符串，则添加到结果中if (count == 4 && start == s.size()) { // 当四个数字都加入的时候才会进入此path.erase(path.end() - 1); // 移除最后一个多余的点res.push_back(path);path += '.';            // 恢复path状态  ？？？？？？？return;}// 如果还没有遍历完字符串，但是已经分了4段，提前返回if (count == 4) return;for (int i = start; i < s.size() && i < start + 3; ++i) { // 最多取3个字符string segment = s.substr(start, i - start + 1);int num = stoi(segment);// 判断数字是否在0-255之间，并且处理前导0的情况if (num <= 255 && (segment == "0" || segment[0] != '0')) {// 追加当前段到路径path += segment + '.'; // 这里没事，当为path为四个的时候去除最后的小数点就ok了count++;backtracking(s, i + 1);count--;// 回溯，移除最后添加的段path.erase(path.length() - segment.length() - 1);}}}
};

通过计数点的数量

#include <vector>
#include <string>
using namespace std;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;}
};

子集问题

子集

• 与组合问题的区别，收获结果时是从每一个节点中去取。
  

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startIndex) {result.push_back(path);if (startIndex >= nums.size()) {return;}for (int i = startIndex; i < nums.size(); i++) {path.push_back(nums[i]);backtracking(nums,i+1);path.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {backtracking(nums,0);return result;}
};

子集II

结果去重

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startIndex) {vector<int> tmp = path;sort(path.begin(), path.end());if (find(result.begin(), result.end(), path) == result.end())  // 标识没有找到{result.push_back(path);}path = tmp;if (startIndex >= nums.size()) {return;}for (int i = startIndex; i < nums.size(); i++) {path.push_back(nums[i]);backtracking(nums,i+1);path.pop_back();}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {backtracking(nums,0);return result;}
};

过程去重

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startIndex, int used[]) {result.push_back(path);if (startIndex >= nums.size()) {return;}for (int i = startIndex; i < nums.size(); i++) {//树层去重：前后两个原始相等，而且已经遍历到相等的第二个元素if (i > 0 && nums[i - 1] == nums[i] && used[i - 1] == 0)continue;path.push_back(nums[i]);used[i] = 1;backtracking(nums,i+1, used);path.pop_back();used[i] = 0;}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(), nums.end());  // 注意一定需要排序int* used = new int[nums.size()];backtracking(nums,0, used);return result;}
};

非递减子序列

直接的思路

/*这里无非就是：子集问题，要求子集内的元素个数>1,子集内元素按从小到大
*/
class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startIndex, int used[]) {if (path.size() > 1){result.push_back(path);}if (startIndex >= nums.size()) {return;}for (int i = startIndex; i < nums.size(); i++) {//树层去重：前后两个原始相等，而且已经遍历到相等的第二个元素if (i > 0 && nums[i - 1] == nums[i] && used[i - 1] == 0)continue;if (!path.empty() && path.back() > nums[i])continue;path.push_back(nums[i]);used[i] = 1;backtracking(nums,i+1, used);path.pop_back();used[i] = 0;}}vector<vector<int>> findSubsequences(vector<int>& nums) {int* used = new int[nums.size()];backtracking(nums,0, used);return result;}
};

树层去重

// 版本一
class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startIndex) {if (path.size() > 1) {result.push_back(path);// 注意这里不要加return，要取树上的节点}//有两种情况不要处理 // 1、非递增不处理 // 2、递增但是会产生重复结果 例如 4、7、7 第一个7要选 第二个7不要选 否则会产生重复结果//用数组去重 一个数组在一层中利用 所以在for循环外面定义unordered_set<int> uset; // 使用set对本层元素进行去重for (int i = startIndex; i < nums.size(); i++) {if ((!path.empty() && nums[i] < path.back())|| uset.find(nums[i]) != uset.end()) {continue;}uset.insert(nums[i]); // 记录这个元素在本层用过了，本层后面不能再用了path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();}}
public:vector<vector<int>> findSubsequences(vector<int>& nums) {result.clear();path.clear();backtracking(nums, 0);return result;}
};

排列问题

全排列

class Solution
{
private:vector<int> path;vector<vector<int>> result;public:void backtracking(vector<int> &nums, vector<int> used){if (path.size() == nums.size()){result.push_back(path);return;}for (int i = 0; i < nums.size(); i++){if (used[i] == 1)continue;path.push_back(nums[i]);used[i] = 1;backtracking(nums, used);path.pop_back();used[i] = 0;}}vector<vector<int>> permute(vector<int> &nums){vector<int> used(nums.size(), 0);backtracking(nums, used);}
};

全排列II

结果去重

class Solution
{
private:vector<int> path;vector<vector<int>> result;public:void backtracking(vector<int> &nums, vector<int> used){if (path.size() == nums.size()){if (find(result.begin(), result.end(), path) == result.end())result.push_back(path);return;}for (int i = 0; i < nums.size(); i++){if (used[i] == 1)continue;path.push_back(nums[i]);used[i] = 1;backtracking(nums, used);path.pop_back();used[i] = 0;}}vector<vector<int>> permuteUnique(vector<int> &nums){vector<int> used(nums.size(), 0);backtracking(nums, used);return result;}
};

在回溯过程中去重

class Solution
{
private:vector<int> path;vector<vector<int>> result;public:void backtracking(vector<int> &nums, vector<int> used){if (path.size() == nums.size()){result.push_back(path);return;}for (int i = 0; i < nums.size(); i++){if ( i>0 && nums[i] == nums[i - 1]&&used[i-1] == 0) //  树层去重：注意前提是数组已经经过排序了，相同元素相邻.//used[i-1] == 0 保证是输层上去重continue;if (used[i] == 1)  // 保证一个数字不会被重复选择continue; path.push_back(nums[i]);used[i] = 1;backtracking(nums, used);path.pop_back();used[i] = 0;}}vector<vector<int>> permuteUnique(vector<int> &nums){sort(nums.begin(), nums.end());vector<int> used(nums.size(), 0);backtracking(nums, used);return result;}
};

棋盘问题

N皇后

class Solution {
public:vector<vector<string>> res;vector<string> target;vector<vector<string>> solveNQueens(int n) {target = vector<string>(n, string(n, '.'));rb(n, 0);return res;}void rb(int n, int row) {if (n == row) {res.push_back(target);return;}for (int i = 0; i < n; i++) {if (!isValid(i, row, n)) {continue;}target[i][row] = 'Q';rb(n, row + 1);target[i][row] = '.';}}bool isValid(int x, int y, int n) {for (int i = 0; i < y; i++) {if (target[x][i] == 'Q')return false;}for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--) {if (target[i][j] == 'Q')return false;}for (int i = x + 1, j = y - 1; i <n && j >= 0; i++, j--) {if (target[i][j] == 'Q')return false;}return true;}
};

解数独问题

class Solution
{
public:bool backtracking(vector<vector<char>> &board){for (int i = 0; i < board.size(); i++){for (int j = 0; j < board[0].size(); j++){if (board[i][j] == '.'){for (char k = '1'; k <= '9'; k++){if (isvalid(board, k, i, j)){board[i][j] = k;if (backtracking(board))return true;board[i][j] = '.';}}return false;}}}return true;}bool isvalid(vector<vector<char>> &board, char val, int row, int col){for (int i = 0; i < 9; i++){if (board[i][col] == val)return false;}for (int j = 0; j < 9; j++){if (board[row][j] == val)return false;}int startrow = (row / 3) * 3;int startcol = (col / 3) * 3;for (int i = startrow; i < startrow + 3; i++){for (int j = startcol; j < startcol + 3; j++){if (board[i][j] == val)return false;}}return true;}void solveSudoku(vector<vector<char>> &board){backtracking(board);}
};