C/C++回溯法
文章目录
- 回溯法
- 组合问题
- 77.组合
- 216.组合总和Ⅲ
- 17.电话号码的字母组合
- 39.组合总和
- 40.组合问题Ⅱ
- 分割问题
- 131.分割回文串
- 93.复原IP地址
- 子集问题
- 78.子集问题
- 90.子集Ⅱ
- 排列问题
- 46.全排列(Medium)
- 47.全排列Ⅱ
- 棋盘问题
- 79.单词搜索(Medium)
- 51.N皇后
- 37.解数独
- 其他
- 491.递增子序列
- 332.重新安排行程
- 总结
回溯法
回溯法(backtracking)是优先搜索的一种特殊情况,又称为试探法,常用于需要记录节点状态的深度优先搜索。通常来说,排列、组合、选择类问题使用回溯法比较方便。
顾名思义,回溯法的核心是回溯。在搜索到某一节点的时候,如果我们发现目前的节点(及其子节点)并不是需求目标时,我们回退到原来的节点继续搜索,并且把在目前节点修改的状态还原。这样的好处是我们可以始终只对图的总状态进行修改,而非每次遍历时新建一个图来储存状态。在具体的写法上,它与普通的深度优先搜索一样,都有 [修改当前节点状态]→[递归子节点] 的步骤,只是多了回溯的步骤,变成了 [修改当前节点状态]→[递归子节点]→[回改当前节点状态]。同时,回溯是递归的副产品,只要有递归就会有回溯。
回溯法修改一般有以下几种情况:
- 组合问题:N个数⾥⾯按⼀定规则找出k个数的集合
- 切割问题:⼀个字符串按⼀定规则有⼏种切割⽅式
- ⼦集问题:⼀个N个数的集合⾥有多少符合条件的⼦集
- 排列问题:N个数按⼀定规则全排列,有⼏种排列⽅式
- 棋盘问题:N皇后,解数独等等
模板如下:
void backtracking(参数) {if (终⽌条件) {存放结果;return;}for (选择:本层集合中元素) {处理节点;backtracking(路径,选择列表); // 递归回溯,撤销处理结果}
}
回溯法性能也并不是特别高效的算法,因为其本质是穷举。列出所有情况,然后选择我们想要的结果。当然,回溯可以进行剪枝等操作。
组合问题
77.组合
题目描述
给定一个整数 n 和一个整数 k,求在 1 到 n 中选取 k 个数字的所有组合方法。
输入输出样例
输入:n = 4, k = 2
输出:
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]
代码
class Solution {
public:void backtrace(int n,int k,vector<int>& path ,int start,vector<vector<int>>& res){if(path.size()==k){res.push_back(path);return;}for(int i=start;i<=n;i++){//for循环可以进行剪枝优化为:for(int i=start;i<=n-(k-path.size())+1;i++){path.push_back(i);backtrace(n,k,path,i+1,res);path.pop_back();}}vector<vector<int>> combine(int n, int k) {vector<vector<int>> res;vector<int> path;backtrace(n,k,path,1,res);return res;}
};
216.组合总和Ⅲ
题目描述
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。
说明:
- 所有数字都是正整数。
- 解集不能包含重复的组合。
输入输出描述
输入: k = 3, n = 7
输出: [[1,2,4]]
代码
class Solution {
public:void dfs(vector<vector<int>>& res,vector<int>& path,int k,int n,int start){if(path.size()==k&&accumulate(path.begin(),path.end(),0)==n){res.push_back(path);return;}//这里同样可以进行剪枝操作,同志们可以想一下怎么剪枝for(int i=start;i<=9;i++){path.push_back(i);dfs(res,path,k,n,i+1);path.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {vector<vector<int>> res;vector<int> path;dfs(res,path,k,n,1);return res;}
};
17.电话号码的字母组合
题目描述
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
** 输入输出样例**
输入:digits = "23"
输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]
代码
class Solution {
public:const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9};vector<string> res;string s;void backtracking(const string& digits,int index){if(index==digits.size()){res.push_back(s);return;}int num=digits[index]-'0';string str=letterMap[num];for(int i=0;i<str.size();i++){s.push_back(str[i]);backtracking(digits,index+1);s.pop_back();}}vector<string> letterCombinations(string digits) {if(digits.empty()) return res;backtracking(digits,0);return res;}
};
39.组合总和
题目描述
给定一个无重复元素的正整数数组 candidates 和一个正整数 target ,找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同,则两种组合是唯一的。
对于给定的输入,保证和为 target 的唯一组合数少于 150 个。
输入输出样例
输入: candidates = [2,3,6,7], target = 7
输出: [[7],[2,2,3]]
代码
class Solution {
public:void backtracking(vector<int>& candidates,int target,int sum,int start,vector<vector<int>>& res,vector<int>& path){if(sum==target){res.push_back(path);return;}if(sum>target) return;for(int i=start;i<candidates.size();i++){sum+=candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,sum,i,res,path);sum-=candidates[i];path.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<vector<int>> res;vector<int> path;backtracking(candidates,target,0,0,res,path);return res;}
};
40.组合问题Ⅱ
题目描述
给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
输入输出样例
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
代码
class Solution {
public:void backtracking(vector<int>& candidates,int target,int sum,int start,vector<vector<int>>& res,vector<int>& path,vector<bool>& isused){if(sum==target){res.push_back(path);return;}if(sum>target) return;for(int i=start;i<candidates.size();i++){//这块好难理解啊!!if(i>0&&candidates[i]==candidates[i-1]&&!isused[i-1]) continue;isused[i]=true;sum+=candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,sum,i+1,res,path,isused);path.pop_back();sum-=candidates[i];isused[i]=false;}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<vector<int>> res;vector<int> path;vector<bool> isused(candidates.size(),false);sort(candidates.begin(),candidates.end());backtracking(candidates,target,0,0,res,path,isused);return res;}
};//使用set去重版本
class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {if (sum == target) {result.push_back(path);return;}unordered_set<int> uset; // 控制某⼀节点下的同⼀层元素不能重复for (int i = startIndex; i < candidates.size() && sum + candidates[i]<= target; i++) {if (uset.find(candidates[i]) != uset.end()) {continue;}uset.insert(candidates[i]); // 记录元素sum += candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i + 1);sum -= candidates[i];path.pop_back();}}
public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {path.clear();result.clear();sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0);return result;}
};
分割问题
131.分割回文串
题目描述
给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
输入输出样例
输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]
代码
class Solution {
public:bool ispalindrome(const string& s,int start,int end){int i=start,j=end;while(i<j){if(s[i]!=s[j]) return false;i++;j--;}return true;}void backtracking(string& s,vector<string>& path,vector<vector<string>>& res,int start){if(start>=s.size()){res.push_back(path);return;}for(int i=start;i<s.size();i++){if(ispalindrome(s,start,i)){string str=s.substr(start,i-start+1);path.push_back(str);}else{continue;}backtracking(s,path,res,i+1);path.pop_back(); // 回溯过程,弹出本次已经填在的⼦串}}vector<vector<string>> partition(string s) {vector<vector<string>> res;vector<string> path;backtracking(s,path,res,0);return res;}
};
93.复原IP地址
题目描述
给定一个只包含数字的字符串,用以表示一个 IP 地址,返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
有效 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 ‘.’ 分隔。
例如:“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址,但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。
输入输出样例
输入:s = "25525511135"
输出:["255.255.11.135","255.255.111.35"]
代码
class Solution {
public:bool isvalid(const string& s,int start,int end){if(start>end) return false;if(s[start]=='0'&&start!=end) 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) return false;}return true;}void backtracking(string& s,vector<string> &res,int pointnum,int start){if(pointnum==3){if(isvalid(s,start,s.size()-1)) res.push_back(s);return;}for(int i=start;i<s.size();i++){if(isvalid(s,start,i)){s.insert(s.begin()+i+1,'.');pointnum++;backtracking(s,res,pointnum,i+2);pointnum--;s.erase(s.begin()+i+1);}}}vector<string> restoreIpAddresses(string s) {vector<string> res;backtracking(s,res,0,0);return res;}
};
子集问题
78.子集问题
题目描述
给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
输入输出样例
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
代码
class Solution {
public:void backtracking(vector<int>& nums,vector<vector<int>>& res,vector<int>& path,int start){res.push_back(path);// 终止条件可加可不加// if(start>=nums.size()){// return;// }for(int i=start;i<nums.size();i++){path.push_back(nums[i]);backtracking(nums,res,path,i+1);path.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> res;vector<int> path;backtracking(nums,res,path,0);return res;}
};
90.子集Ⅱ
题目描述
给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。
输入输出样例
输入:nums = [1,2,2]
输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]
代码
class Solution {
public:void backtracking(vector<int>& nums,vector<vector<int>>& res,vector<int>& path,int start){res.push_back(path);unordered_set<int> uset;for(int i=start;i<nums.size();i++){if(uset.find(nums[i])!=uset.end()){continue;}uset.insert(nums[i]);path.push_back(nums[i]);backtracking(nums,res,path,i+1);path.pop_back();}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {vector<vector<int>> res;vector<int> path;sort(nums.begin(),nums.end());backtracking(nums,res,path,0);return res;}
};
排列问题
46.全排列(Medium)
题目描述
给定一个无重复数字的整数数组,求其所有的排列方式。
输入输出样例
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
题解
代码
class Solution {
public:void backtrace(const vector<int>& nums,vector<int>& path,vector<bool>& isTrace,vector<vector<int>>& res){if(path.size()==nums.size()){res.push_back(path);return;}for(int i=0;i<nums.size();i++){if(isTrace[i]){continue;}isTrace[i]=true;path.push_back(nums[i]);backtrace(nums,path,isTrace,res);path.pop_back();isTrace[i]=false;}}vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> res;if(nums.empty()) return res;vector<bool> isTrace(nums.size(),false);vector<int> path;backtrace(nums,path,isTrace,res);return res;}
};
47.全排列Ⅱ
题目描述
给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。
输入输出样例
输入:nums = [1,1,2]
输出:
[[1,1,2],[1,2,1],[2,1,1]]
题解
套路跟之前都是相同的,但是这题强调的是去重,所以要对元素进行排序。
这里引用一下代码随想录的题解图:
如果前一位nums[i-1]如果使用过,就进行去重,但是从理解上又分为 树层去重 和 树枝去重。
即下面两段关键代码:
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;
}
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) {continue;
}
下面用代码随想录的例子解释一下:
代码
class Solution {
public:void backtracking(vector<int>& nums,vector<vector<int>>& res,vector<int>& path,vector<bool>& used){if(nums.size()==path.size()){res.push_back(path);return;}for(int i=0;i<nums.size();i++){// used[i - 1] == true,说明同⼀树⽀nums[i - 1]使⽤过// used[i - 1] == false,说明同⼀树层nums[i - 1]使⽤过// 如果同⼀树层nums[i - 1]使⽤过则直接跳过if((i>0&&nums[i]==nums[i-1]&&used[i-1])||used[i]){continue;}used[i]=true;path.push_back(nums[i]);backtracking(nums,res,path,used);path.pop_back();used[i]=false;}}vector<vector<int>> permuteUnique(vector<int>& nums) {vector<vector<int>> res;vector<int> path;vector<bool> used(nums.size(),false);sort(nums.begin(),nums.end());backtracking(nums,res,path,used);return res;}
};
棋盘问题
79.单词搜索(Medium)
题目描述
给定一个字母矩阵,所有的字母都与上下左右四个方向上的字母相连。给定一个字符串,求字符串能不能在字母矩阵中寻找到。
输入输出样例
输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出:true
代码
class Solution {
public:void dfs(vector<vector<char>>& board,string& word,int r,int c,bool& flag,vector<vector<bool>>& visited,int pos){if(r<0||r>=board.size()||c<0||c>=board[0].size()){return;}if(visited[r][c]||flag||board[r][c]!=word[pos]){return;}if(pos==word.size()-1){flag=true;return;}visited[r][c]=true;dfs(board,word,r+1,c,flag,visited,pos+1);dfs(board,word,r-1,c,flag,visited,pos+1);dfs(board,word,r,c+1,flag,visited,pos+1);dfs(board,word,r,c-1,flag,visited,pos+1);visited[r][c]=false;}bool exist(vector<vector<char>>& board, string word) {vector<vector<bool>> visited(board.size(),vector<bool>(board[0].size(),false));bool flag=false;for(int i=0;i<board.size();i++){for(int j=0;j<board[0].size();j++){dfs(board,word,i,j,flag,visited,0);}}return flag;}
};
51.N皇后
题目描述
给定一个大小为 n 的正方形国际象棋棋盘,求有多少种方式可以放置 n 个皇后并使得她们互不攻击,即每一行、列、左斜、右斜最多只有一个皇后。
输入输出描述
输入:n = 4
输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释:如上图所示,4 皇后问题存在两个不同的解法。点代表空白位置,Q 代表皇后。
代码
class Solution {
public:vector<vector<string>> result;// n 为输⼊的棋盘⼤⼩// row 是当前递归到棋牌的第⼏⾏了void backtracking(int n, int row, vector<string>& chessboard) {if (row == n) {result.push_back(chessboard);return;}for (int col = 0; col < n; col++) {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) {int count = 0;// 检查列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;}vector<vector<string>> solveNQueens(int n) {result.clear();std::vector<std::string> chessboard(n, std::string(n, '.'));backtracking(n, 0, chessboard);return result;}
};
37.解数独
题目描述
编写一个程序,通过填充空格来解决数独问题。
数独的解法需 遵循如下规则:
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)
数独部分空格内已填入了数字,空白格用 ‘.’ 表示。
输入输出样例
输入:board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出:[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释:输入的数独如上图所示,唯一有效的解决方案如下所示:
代码
class Solution {
private: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] != '.') continue;for (char k = '1'; k <= '9'; k++) { // (i, j) 这个位置放k是否合适if (isValid(i, j, k, board)) {board[i][j] = k; // 放置kif (backtracking(board)) return true; // 如果找到合适⼀组⽴刻返回board[i][j] = '.'; // 回溯,撤销k}}return false; // 9个数都试完了,都不⾏,那么就返回false}}return true; // 遍历完没有返回false,说明找到了合适棋盘位置了}bool isValid(int row, int col, char val, vector<vector<char>>& board) {for (int i = 0; i < 9; i++) { // 判断⾏⾥是否重复if (board[row][i] == val) {return false;}}for (int j = 0; j < 9; j++) { // 判断列⾥是否重复if (board[j][col] == val) {return false;}}int startRow = (row / 3) * 3;int startCol = (col / 3) * 3;for (int i = startRow; i < startRow + 3; i++) { // 判断9⽅格⾥是否重复for (int j = startCol; j < startCol + 3; j++) {if (board[i][j] == val ) {return false;}}}return true;}public:void solveSudoku(vector<vector<char>>& board) {backtracking(board);}
};
其他
491.递增子序列
题目描述
给你一个整数数组 nums ,找出并返回所有该数组中不同的递增子序列,递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素,如出现两个整数相等,也可以视作递增序列的一种特殊情况。
输入输出样例
输入:nums = [4,6,7,7]
输出:[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
题解
这道题类似子集问题,但是又有所不同。一个是要去除重复使用过的元素,另一个是判断加入元素要是递增的
代码
class Solution {
public:void backtracking(vector<int>& nums,vector<vector<int>>& res,vector<int>& path,int start){if(path.size()>=2){res.push_back(path);}int used[201]={0};for(int i=start;i<nums.size();i++){if((!path.empty()&&nums[i]<path.back())||used[nums[i]+100]==1){continue;}used[nums[i]+100]=1; //元素在本层已经使用过了,本层后面不能再用path.push_back(nums[i]);backtracking(nums,res,path,i+1);path.pop_back();}}vector<vector<int>> findSubsequences(vector<int>& nums) {vector<vector<int>> res;vector<int> path;backtracking(nums,res,path,0);return res;}
};
332.重新安排行程
题目描述
给你一份航线列表 tickets ,其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 开始。如果存在多种有效的行程,请你按字典排序返回最小的行程组合。
- 例如,行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小,排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
输入输出样例
输入:tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出:["JFK","MUC","LHR","SFO","SJC"]
代码
class Solution {
public:// unordered_map<出发机场, map<到达机场, 航班次数>> targetsunordered_map<string, map<string, int>> targets;bool backtracking(int ticketNum, vector<string>& result) {if (result.size() == ticketNum + 1) {return true;}for (pair<const string, int>& target : targets[result[result.size() - 1]]){if (target.second > 0 ) { // 记录到达机场是否⻜过了result.push_back(target.first);target.second--;if (backtracking(ticketNum, result)) return true;result.pop_back();target.second++;}}return false;}vector<string> findItinerary(vector<vector<string>>& tickets) {targets.clear();vector<string> result;for (const vector<string>& vec : tickets) {targets[vec[0]][vec[1]]++; // 记录映射关系}result.push_back("JFK"); // 起始机场backtracking(tickets.size(), result);return result;}
};
总结
回溯主要是要考虑清楚以下几个问题:
- 如何理解回溯法的搜索过程
- 什么时候⽤startIndex,什么时候不⽤?
- 如何去重?如何理解“树枝去重”与“树层去重”?
- 去重的⼏种⽅法?
- 如何理解⼆维递归?
参考资料:代码随想录
更多推荐
C/C++回溯法
发布评论