第77题. 组合
链接：代码随想录
class Solution { public:vector<vector<int>> v;vector<int>res;vector<vector<int>> combine(int n, int k) {backtracing(n,1,k);return v;}void backtracing(int n,int startIndex,int k){if(res.size()==k){v.push_back(res);//res.clear();return;}for(int j=startIndex;j<=n;j++){res.push_back(j);backtracing(n,j+1,k);res.pop_back();}} };剪枝：
class Solution { public:vector<vector<int>> v;vector<int>res;vector<vector<int>> combine(int n, int k) {backtracing(n,1,k);return v;}void backtracing(int n,int startIndex,int k){if(res.size()==k){v.push_back(res);//res.clear();return;}for(int j=startIndex;j<=n - (k - res.size()) + 1;j++){res.push_back(j);backtracing(n,j+1,k);res.pop_back();}} };
216. 组合总和 III
链接：力扣
剪枝注意：
class Solution { public:vector<vector<int>>v;vector<int>res;vector<vector<int>> combinationSum3(int k, int n) {backtracing(k,n,1);return v;}void backtracing(int k,int n,int startIndex){if(res.size()==k && n==0){v.push_back(res);}for(int j=startIndex;j<=9-(k-res.size())+1;j++){res.push_back(j);if(n-j>=0){backtracing(k,n-j,j+1);}res.pop_back();}} };a
17.电话号码的字母组合
链接：力扣
自己的做法：
class Solution { public:vector<string>v;vector<string>res;string str;vector<string> letterCombinations(string digits) {if(digits==""){return v;}v.push_back("abc");v.push_back("def");v.push_back("ghi");v.push_back("jkl");v.push_back("mno");v.push_back("pqrs");v.push_back("tuv");v.push_back("wxyz");backtracing(v,0,digits);return res;}void backtracing(vector<string> &v,int digitsIndex,string &digits){if(digitsIndex==digits.size()){res.push_back(str);}else{string s=v[digits[digitsIndex]-'2'];cout<<s<<endl;for(int j=0;j<s.size();j++){str.push_back(s[j]);backtracing(v, digitsIndex+1,digits);str.pop_back();}}} };a
39. 组合总和
链接：代码随想录
class Solution { public:vector<vector<int>>v;vector<int>res;vector<vector<int>> combinationSum(vector<int>& candidates, int target) {int n=candidates.size();if(n==0){return v;}backtracing(candidates,target,0,n);return v;}void backtracing(vector<int> & candidates,int target,int startIndex,int n){if(target==0){v.push_back(res);}for(int j=startIndex;j<n;j++){if(target-candidates[j]>=0){res.push_back(candidates[j]);backtracing(candidates,target-candidates[j],j,n);res.pop_back();}}} };
40.组合总和II
链接：代码随想录
class Solution { public:vector<vector<int>> v;vector<int>res;vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {int n=candidates.size();if(n==0){return v;}sort(candidates.begin(),candidates.end());backtracing(candidates,target,0,n);return v;}void backtracing(vector<int>& candidates, int target,int startIndex,int n){if(target==0){v.push_back(res);}for(int j=startIndex;j<n;j++){if(j>startIndex && candidates[j]==candidates[j-1]){continue;}if(target-candidates[j]>=0){res.push_back(candidates[j]);backtracing(candidates,target-candidates[j],j+1,n);res.pop_back();}}} };a
131.分割回文串
链接：力扣
自己的解法，欣喜若狂的做对了
class Solution {//牢记分割回文串这道题是回溯//牢记是组合问题，而且startIndex就是隔板 public:vector<vector<string>> v;vector<string>res;vector<vector<string>> partition(string s) {int n=s.size();if(n==0){return v;}backtracing(s,0,n);return v;}void backtracing(string s,int startIndex,int n){if(startIndex==n){v.push_back(res);}for(int j=startIndex;j<n;j++){string str=s.substr(startIndex,j-startIndex+1);if(is_huiwen(str)){res.push_back(str);backtracing(s,j+1,n);res.pop_back();}}}bool is_huiwen(string &str){int right=str.size()-1;int left=0;while(left<right){if(str[left]!=str[right]){return false;}left++;right--;}return true;} };
93.复原IP地址
链接：代码随想录
挺震惊的，我写的还挺快的
class Solution { public:vector<string>v;//string res="";vector<string> restoreIpAddresses(string s) {backtracing(s,0,s.size(),0,"");return v;}void backtracing(string &s,int startIndex,int n,int k,string res)//k代表已经加入的一个小数点个数{if(startIndex==n && k==4){res.pop_back();v.push_back(res);}for(int j=startIndex;j<n;j++){string str=s.substr(startIndex,j-startIndex+1);if(str.size()>1 && str[0]=='0'){continue;}if(str.size()<=3){int num=atoi(str.c_str());if(num>=0 && num<=255){backtracing(s,j+1,n,k+1,res+str+"."); }}}} };a
78. 子集
链接：代码随想录
吓人。。。。今天的代码都是一次对
代码：
class Solution { public:vector<vector<int>> v;vector<int>res;vector<vector<int>> subsets(vector<int>& nums) {int n=nums.size();backtracing(nums,0,n);return v;}void backtracing(vector<int>& nums,int startIndex,int n){if(res.size()<=n ){v.push_back(res);}for(int j=startIndex;j<n;j++){res.push_back(nums[j]);backtracing(nums,j+1,n);res.pop_back();}} };a
a
90. 子集 II
链接：力扣
还是那套模板
class Solution { public:vector<vector<int>>v;vector<int>mv;vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(),nums.end());backtracing(nums,0);return v;}void backtracing(vector<int> &nums,int startIndex){if(mv.size()<=nums.size()){v.push_back(mv);}for(int j=startIndex;j<nums.size();j++){if(j>startIndex && nums[j]==nums[j-1]){continue;}mv.push_back(nums[j]);backtracing(nums,j+1);mv.pop_back();}} };
491.递增子序列 ---------没思路
链接：代码随想录
看了答案，主要是横向扩展节点时要做约束
答案：
力扣
46.全排列 ----------------------写错，排列掌握的没有组合好
链接：代码随想录
错误写法：我也不知道咋发明的，还是理解上错误，貌似我这样写约束的是纵向，打印结果只有一种。但是正确解法是每个节点上横向扩展，比如【1，2，3】第一层已经选了1，那么就平等的试一下选2、选3，选完就used，也就是节点上横向扩展。
所以
class Solution { public:vector<bool>used;vector<vector<int>>v;vector<int>res;vector<vector<int>> permute(vector<int>& nums) {int n=nums.size();used.resize(n,false);backtracing(nums,0,n);return v;}void backtracing(vector<int>&nums,int i,int n){if(i==n){v.push_back(res);}for(int j=0;j<n;j++){if(!used[j]){used[i]=true;res.push_back(nums[i]);backtracing(nums,i+1,n);res.pop_back();used[i]=false;}}} };正确答案：
class Solution { public:vector<bool>used;vector<vector<int>>v;vector<int>res;vector<vector<int>> permute(vector<int>& nums) {int n=nums.size();used.resize(n,false);backtracing(nums,n);return v;}void backtracing(vector<int>&nums,int n){if(res.size()==n){v.push_back(res);}for(int j=0;j<n;j++){if(!used[j]){used[j]=true;res.push_back(nums[j]);backtracing(nums,n);res.pop_back();used[j]=false;}}} };a
47.全排列||
class Solution { public: //关键词：可包含重复数字的序列 nums的排列问题 //排列：一定用到used数组。而且每一层都从0开始遍历，遍历used数组中未标记的 //可重，要先排序，对于横向展开的选择再去重，和组合思路一样 vector<vector<int>>v; vector<int>mv;vector<vector<int>> permuteUnique(vector<int>& nums) {v.clear();mv.clear();vector<bool>used;used.resize(nums.size(),false);sort(nums.begin(),nums.end());//先排序再去重backtracing(nums,used);return v;}void backtracing(vector<int> &nums,vector<bool> &used){if(mv.size()==nums.size()){v.push_back(mv);}for(int j=0;j<nums.size();j++){if (j > 0 && nums[j] == nums[j - 1] && used[j- 1] == false) {continue;}if(used[j]==false){used[j]=true;mv.push_back(nums[j]);backtracing(nums,used);mv.pop_back();used[j]=false;}}} };
51. N皇后
链接：代码随想录
class Solution { public:vector<vector<string>>v;vector<string>board;vector<vector<string>> solveNQueens(int n) {board.resize(n,string(n,'.'));backtracing(board,0,n);return v;}void backtracing(vector<string>&board,int i,int n){if(i==n){v.push_back(board);}for(int j=0;j<n;j++){if(if_can(board,i,j,n)){board[i][j]='Q';backtracing(board,i+1,n);board[i][j]='.';}}}bool if_can(vector<string>&board,int i,int j,int n){//不同列for(int k=0;k<i;k++){if(board[k][j]=='Q'){return false;}}//左上角检查int x=i;int y=j;while(x>=0 && y>=0&&x<n &&y<n){if(board[x][y]=='Q'){return false;}x--;y--;}x=i;y=j;//右上角检查while(x>=0 && y>=0&&x<n &&y<n){if(board[x][y]=='Q'){return false;}x--;y++;}return true;}};
52. N 皇后 II-----应该没啥问题
链接：力扣
class Solution { public://记录之前的Q的位置;vector<pair<int,int>>location;int cnt=0;int totalNQueens(int n) {backtracing(0,n);return cnt;}void backtracing(int i,int n){if(i==n){cnt++;}for(int j=0;j<n;j++){if(if_can(i,j,n)){location.push_back({i,j});backtracing(i+1,n);location.pop_back();}}}bool if_can(int i,int j,int n){//同一列for(auto p:location){//同一列if(p.second==j){return false;}//左上角 //右上角if(((i-p.first)==(j-p.second))||((i-p.first)==(p.second-j))){return false;}}return true;} };
37. 解数独
链接：代码随想录
大概看了一下答案，重点在于三次循环。
错了一些，重点是回溯是一个bool，找到合适的立即返回结果，不合适的不返回。这样能防止超时。
class Solution { public:void solveSudoku(vector<vector<char>>& board) {int n=board.size();int m=board[0].size();backtracing(board,n,m);}bool backtracing(vector<vector<char>>&board,int n,int m){for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(board[i][j]!='.'){continue;}for(int k='1';k<='9';k++){if(is_Valid(i,j,k,board)){board[i][j]=k;if (backtracing(board,n,m)) return true; // 如果找到合适一组立刻返回board[i][j]='.';}}return false; // 9个数都试完了，都不行，那么就返回false}}return true;}bool is_Valid(int i,int j,char ch,vector<vector<char>>&board){//同一列，检查for(int t=0;t<9;t++){if(board[t][j]==ch){return false;}}//同一行，检查for(int t=0;t<9;t++){if(board[i][t]==ch){return false;}}int n=i/3;int m=j/3;for(int t=n*3;t<n*3+3;t++){for(int k=3*m;k<3*m+3;k++){if(board[t][k]==ch){return false;}}}return true;} };
