77. 组合
class Solution {
public:vector<int> path;vector<vector<int>> res;//确定递归函数参数和返回值void backtracking(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);backtracking(n,k,i+1);path.pop_back();}}vector<vector<int>> combine(int n, int k) {backtracking(n,k,1);return res;}
};剪枝优化：（对每层循环遍历的范围进行了缩小）
class Solution {
public:vector<int> path;vector<vector<int>> res;//确定递归函数参数和返回值void backtracking(int n,int k,int startIndex){//确定终止条件if(path.size()==k){res.push_back(path);return;}//确定单层递归逻辑for(int i=startIndex;i<=n-(k-path.size())+1;i++){//优化的地方path.push_back(i);backtracking(n,k,i+1);path.pop_back();}}vector<vector<int>> combine(int n, int k) {backtracking(n,k,1);return res;}
};216. 组合总和 III
class Solution {
public:vector<int>path;vector<vector<int>>res;//确定递归函数参数和返回值void backtracking(int k,int n,int startIndex){//确定终止条件if(path.size()==k){if(n==0){res.push_back(path);return;}}//确定单层递归逻辑for(int i=startIndex;i<=9;i++){n-=i;path.push_back(i);backtracking(k,n,i+1);path.pop_back();n+=i;}}vector<vector<int>> combinationSum3(int k, int n) {backtracking(k,n,1);return res;}
};剪枝优化：
1.目标数n一直在随i的加入减小，如果目标数n已经<0，那么剪枝。即path中的数已经大于目标数了。
2.对for循环i的遍历范围进行缩小
class Solution {
public:vector<int>path;vector<vector<int>>res;//确定递归函数参数和返回值void backtracking(int k,int n,int startIndex){//优化：剪枝if(n<0) return;//确定终止条件if(path.size()==k){if(n==0){res.push_back(path);return;}}//确定单层递归逻辑for(int i=startIndex;i<=10-(k-path.size());i++){//剪枝 优化n-=i;path.push_back(i);backtracking(k,n,i+1);path.pop_back();n+=i;}}vector<vector<int>> combinationSum3(int k, int n) {backtracking(k,n,1);return res;}
};17. 电话号码的字母组合
class Solution {
public:const string letterMap[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz",};vector<string> res;string s;//确定递归函数参数和返回值void backtracing(const string& digits,int index){//确定终止条件if(index==digits.size()){res.push_back(s);return;}//确定单层递归逻辑int num=digits[index]-'0';//string str=letterMap[num];string strr=letterMap[num];for(int i=0;i<strr.size();i++){s.push_back(strr[i]);backtracing(digits,index+1);s.pop_back();}}vector<string> letterCombinations(string digits) {if(digits.size()==0){return res;}backtracing(digits,0);return res;}
};39. 组合总和
class Solution {
public:vector<int> path;vector<vector<int>>res;//确定递归函数参数和返回值void backtracking(vector<int>& candidates,int target,int startIndex){//确定终止条件if(target<0) return;if(target==0) {res.push_back(path);return;}//确定单层递归逻辑for(int i=startIndex;i<candidates.size();i++){target-=candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,i);target+=candidates[i];path.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backtracking(candidates,target,0);return res;}
};优化：（剪枝）
优化后的比之前的在叶子结点少递归一层。在排序candidates后，碰到target<0的情况直接结束本层的遍历，后面没遍历到的也不用遍历了。
class Solution {
public:vector<int> path;vector<vector<int>>res;//确定递归函数参数和返回值void backtracking(vector<int>& candidates,int target,int startIndex){//确定终止条件if(target==0) {res.push_back(path);return;}//确定单层递归逻辑for(int i=startIndex;i<candidates.size()&&target-candidates[i]>=0;i++){target-=candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,i);target+=candidates[i];path.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {sort(candidates.begin(),candidates.end());backtracking(candidates,target,0);return res;}
};40. 组合总和 II
class Solution {
public:vector<int>path;vector<vector<int>>res;//确定递归函数参数和返回值void backtracking(vector<int>& candidates,int target,vector<bool>st,int startIndex){//确定终止条件if(target<0)return;if(target==0){res.push_back(path);return;}//确定单层递归逻辑for(int i=startIndex;i<candidates.size();i++){if(i>0&&candidates[i]==candidates[i-1]&&st[i-1]==false){continue;}//对组合去重path.push_back(candidates[i]);st[i]=true;target-=candidates[i];backtracking(candidates,target,st,i+1);path.pop_back();st[i]=false;target+=candidates[i];}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<bool>st(candidates.size(),false);sort(candidates.begin(),candidates.end());backtracking(candidates,target,st,0);return res;}
};131. 分割回文串
class Solution {
public://确定是否是回文bool isTrue(string s,int start,int end){for(int i=start,j=end;i<j;){if(s[i]!=s[j]){return false;}else {i++;j--;}}return true;}//确定递归函数参数和返回值void backtracking(vector<string>& path,vector<vector<string>>& res,int startIndex,string s){//确定终止条件if(startIndex==s.size()){res.push_back(path);return;}//确定单层递归逻辑for(int i=startIndex;i<s.size();i++){if(isTrue(s,startIndex,i)){string str=s.substr(startIndex,i-startIndex+1);path.push_back(str);}else{continue;}backtracking(path,res,i+1,s);path.pop_back();}}vector<vector<string>> partition(string s) {vector<string>path;vector<vector<string>>res;backtracking(path,res,0,s);return res;}
};93. 复原 IP 地址
class Solution {
public://确判断是否符合ip地址bool isTrue(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]<'0'||s[i]>'9') return false;num=num*10+(s[i]-'0');if(num>255)return false;}return true;}//确定递归函数参数和返回值void backtracking(string &s,int startIndex,int pointNum,vector<string>&res){//确定终止条件if(pointNum==3){if(isTrue(s,startIndex,s.size()-1)){res.push_back(s);}return;}//确定单层递归逻辑for(int i=startIndex;i<s.size();i++){if(isTrue(s,startIndex,i)){s.insert(s.begin()+i+1,'.');pointNum+=1;backtracking(s,i+2,pointNum,res);pointNum-=1;s.erase(s.begin()+i+1);}else break;}}vector<string> restoreIpAddresses(string s) {vector<string>res;if(s.size()<4||s.size()>12) return res;backtracking(s,0,0,res);return res;}
};78. 子集
class Solution {
public:vector<int>path;vector<vector<int>>res;//确定递归函数参数和返回值void backtracking(int startIndex,vector<int>nums){res.push_back(path);//不会漏掉自己，空集//确定终止条件if(startIndex>=nums.size()) return;//确定单层递归逻辑for(int i=startIndex;i<nums.size();i++){path.push_back(nums[i]);backtracking(i+1,nums);path.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {backtracking(0,nums);return res;}
};90. 子集 II
class Solution {
public:vector<int>path;vector<vector<int>>res;//确定递归函数参数和返回值void backtracking(vector<int>nums,int startIndex,vector<bool>&st){res.push_back(path);//确定终止条件if(startIndex>=nums.size())return;//确定单层递归逻辑for(int i=startIndex;i<nums.size();i++){if(i>0&&nums[i]==nums[i-1]&&st[i-1]==false){continue;}path.push_back(nums[i]);st[i]=true;backtracking(nums,i+1,st);path.pop_back();st[i]=false;}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {vector<bool> st(nums.size(),false);sort(nums.begin(),nums.end());backtracking(nums,0,st);return res;}
};也可以不用st数组去重
class Solution {
public:vector<int>path;vector<vector<int>>res;//确定递归函数参数和返回值void backtracking(vector<int>nums,int startIndex){res.push_back(path);//确定终止条件if(startIndex>=nums.size())return;//确定单层递归逻辑for(int i=startIndex;i<nums.size();i++){if(i>startIndex&&nums[i]==nums[i-1]){continue;}path.push_back(nums[i]);backtracking(nums,i+1);path.pop_back();}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(),nums.end());backtracking(nums,0);return res;}
};491. 非递减子序列
class Solution {
public:vector<int>path;vector<vector<int>>res;//确定递归函数参数和返回值void backtracking(vector<int>& nums,int startIndex){if(path.size()>1){res.push_back(path);}//确定终止条件if(startIndex>=nums.size()){return;}//确定单层递归逻辑unordered_set<int> uset;//对每层去重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();}}vector<vector<int>> findSubsequences(vector<int>& nums) {backtracking(nums,0);return res;}
};利用数组去重，因为题目的数值范围小，所以可以尽量使用。
class Solution {
public:vector<int>path;vector<vector<int>>res;//确定递归函数参数和返回值void backtracking(vector<int>& nums,int startIndex){if(path.size()>1){res.push_back(path);}//确定终止条件if(startIndex>=nums.size()){return;}//确定单层递归逻辑int st[201]={0};//对每层去重for(int i=startIndex;i<nums.size();i++){if((!path.empty()&&nums[i]<path.back())||st[nums[i]+100]==1){continue;}st[nums[i]+100]=1;;//记录该元素在本层用过了，之后的相同元素不再使用path.push_back(nums[i]);backtracking(nums,i+1);path.pop_back();}}vector<vector<int>> findSubsequences(vector<int>& nums) {backtracking(nums,0);return res;}
};46. 全排列
class Solution {
public:vector<int>path;vector<vector<int>>res;//确定递归函数参数和返回值void backtracking(vector<int>& nums,vector<bool>& st){//确定终止条件if(path.size()==nums.size()){res.push_back(path);return;}//确定单层递归逻辑for(int i=0;i<nums.size();i++){if(st[i]==true) continue;st[i]=true;path.push_back(nums[i]);backtracking(nums,st);path.pop_back();st[i]=false;}}vector<vector<int>> permute(vector<int>& nums) {vector<bool> st(nums.size(),false);backtracking(nums,st);return res;}
};47. 全排列 II
class Solution {
public:vector<int>path;vector<vector<int>>res;//确定递归函数参数和返回值void backtracking(vector<int>& nums,vector<bool>& st){//确定终止条件if(path.size()==nums.size()){res.push_back(path);return;}//确定单层递归逻辑for(int i=0;i<nums.size();i++){if(i>0&&nums[i]==nums[i-1]&&st[i-1]==false){continue;//树层去重的}if(st[i]==true) continue;//树枝去重st[i]=true;path.push_back(nums[i]);backtracking(nums,st);path.pop_back();st[i]=false;}}vector<vector<int>> permuteUnique(vector<int>& nums) {vector<bool>st(nums.size(),false);sort(nums.begin(),nums.end());backtracking(nums,st);return res;}
};332. 重新安排行程
class Solution {
public://unordered_map<出发机场,map<到达机场,航班次数>>targets;unordered_map<string,map<string,int>>targets;//确定递归函数参数和返回值bool backtracking(int ticketNum,vector<string>& res){//确定终止条件if(res.size()==ticketNum+1){return true;}//确定单层递归逻辑for(pair<const string, int>&target:targets[res[res.size()-1]]){if(target.second>0){//记录到达机场是否飞过了res.push_back(target.first);target.second--;if(backtracking(ticketNum,res)) return true;res.pop_back();target.second++;}}return false;}vector<string> findItinerary(vector<vector<string>>& tickets) {vector<string>res;for(const vector<string>& vec:tickets){targets[vec[0]][vec[1]]++;//记录映射关系}res.push_back("JFK");backtracking(tickets.size(),res);return res;}
};51. N 皇后
class Solution {
public:vector<vector<string>>res;//判断位置是否合法bool isValid(int n,int col,int row,vector<string>& chessBorad){//同一列for(int i=row-1;i>=0;i--){if(chessBorad[i][col]=='Q')return false;}//东北夹角for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++){if(chessBorad[i][j]=='Q') return false;}//西北夹角for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){if(chessBorad[i][j]=='Q') return false;}return true;}//确定递归函数参数和返回值void backtracking(int n,int row,vector<string>& chessBorad){//确定终止条件if(n==row){res.push_back(chessBorad);return ;}//确定单层递归逻辑for(int col=0;col<n;col++){if(!isValid(n,col,row,chessBorad)){continue;}else{chessBorad[row][col]='Q';backtracking(n,row+1,chessBorad);chessBorad[row][col]='.';}}}vector<vector<string>> solveNQueens(int n) {vector<string> chessBorad(n,string(n,'.'));backtracking(n,0,chessBorad);return res;}
};37. 解数独
class Solution {
public: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 i=0;i<9;i++){if(board[i][col]==val) return false;} //九宫格内判断row=(row/3)*3;col=(col/3)*3;for(int i=row;i<row+3;i++){for(int j=col;j<col+3;j++){if(board[i][j]==val) return false;}}return true;}bool backtracking(vector<vector<char>>& board){//不需要单独的终止条件，不需要收集结果//确定单层递归逻辑for(int row=0;row<board.size();row++){for(int col=0;col<board[0].size();col++){if(board[row][col]=='.'){for(char val='1';val<='9';val++){if(isValid(row,col,val,board)){board[row][col]=val;if(backtracking(board)) return true;board[row][col]='.';}}return false;}}}return true;}void solveSudoku(vector<vector<char>>& board) {backtracking(board);}
};
