五大经典算法二回溯

程序员文章站 2024-02-20 14:25:52

...

回溯算法在解决多选择问题时特别有效，一般思路如下：在当前场景下，存在若干种选择去操作，有可能两种结果：一是违反相应条件限制，只能返回（back），另一种是该选择选到最后居然正确并结束。故在回溯时存在三要素，能总结出这样的三要素问题便可以迅速解决：

1 找到选择

2 限制条件，即选择操作在此条件下才进行

3 结束

回溯在迷宫问题等应用广泛，下面的Leetcode22题Generate Parentheses 也是很典型的回溯问题。

Generate Parenthese要求给出n对括号下的所有可能例如

n=3

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

从题目寻找三要素：

1 选择：

加左括号

加右括号

2 条件

左括号没有用完（才可以加左括号）

右括号数目小于左括号数目（才可以加右括号）

3 结束

左右括号均用完

思路：





if (左右括号都已用完) {



  加入解集，返回



}



//否则开始试各种选择




if (还有左括号可以用) {



  加一个左括号，继续递归



}




if (右括号小于左括号) {



  加一个右括号，继续递归



}

代码：




void backtrade(string sublist,vector<string> &res,int left,int right)//left 是左括号剩余



{



    if(left==0&&right==0){res.push_back(sublist);return;



                           }//左右括号用完




    if(left>0){backtrade(sublist+"(",res,left-1,right);}//左括号可以用




    if(left<right){backtrade(sublist+")",res,left,right-1);}



}




vector<string> generateParenthesis(int n){



    vector<string> res;



    backtrade("",res,n,n);



    return res;



                                          }

是一个非常典型的套路，有许多题都会用到，基本上大部分NP问题的求解都是用这个方式，比如N-Queens，Sudoku Solver，Combination Sum，Combinations，Permutations，Word Break II，Palindrome Partitioning等，所以大家只要把这个套路掌握熟练

例如Leetcode 51. N-Queens
当n=4时，4X4棋盘有两种摆法（Q代表皇后，.表示空白）：




[



 [".Q..",  // Solution 1




  "...Q",



  "Q...",



  "..Q."],



 



 ["..Q.",  // Solution 2




  "Q...",



  "...Q",



  ".Q.."]



]

这类NP问题时间复杂度肯定是指数量级，解题思路是回溯，即通过循环下递归，条件约束回溯，直到满足结束条件。在这里回溯三要素：

一选择：添加Q还是点

二条件：满足NQueens布局条件

三所有行都满足条件时存储棋盘并结束

定义一个数组colForrow[n]，colForrow[i]=j代表第i行第j列上是皇后。这是问题的需要耗费的空间复杂度O(N)

问题的首先需要检查加入当前皇后的合法性：

检查行：即当前行row不存在第二个皇后;

检查列：即当前列不存在第二个皇后;

因为我们采用逐行求解，故在当前行布置皇后前该行全部空白自动满足，主要考虑列，即当前行与前面的不冲突。

检查对角线：就是行的差和列的差的绝对值不要相等就可以。

总体设计思路：

采用循环递归机制即在每一层递归函数内，用一个循环（循环是针对列的循环）把一个皇后填入对应行的每一列，如果当前加入第j列棋盘合法则递归处理下一行，如果在处理下一行时发现遍历所有列都不能满足棋盘规则，则退出该层递归，回溯返回到上一行。注意此时不用再把添加的元素移除，因为这里用的是一个一维数组去存皇后在对应行的哪一列，当回溯到上一行时该数组自动回到原来状态。在进入上一行后，由于循环将列数j加1继续判断。直到所有行都完成保存结果并结束




//Queens




string vectorcharTostring(vector<char> ss){



    string res="";



    for(int i=0;i<ss.size();i++)



 res+=ss[i];



    res+='\0';



    return res;



                                            }



bool checkValidQueen(int row,int colForrow[])



{




for(int i=0;i<row;i++)



    if(colForrow[row]==colForrow[i]||abs(colForrow[row]-colForrow[i])==row-i)return 0;




return 1;



}//除了刚加的，前面的都是合法，故只需检查当前行和前面




void helper_queen(int n,int row,int colForrow[], vector< vector<string> >& res)



{



    if(row==n){



    vector<string> item;



    for(int i=0;i<n;i++)



    {



       vector<char> strRow;



     for(int j=0;j<n;j++)



        if(colForrow[i]==j)strRow.push_back('Q');



            else strRow.push_back('.');



     string tmp=vectorcharTostring(strRow);



       item.push_back(tmp);



 }



   //for(int i=0;i<item.size();i++)cout<<item[i]<<endl;




   res.push_back(item);//存储完毕




    return;



               }



    for(int i=0;i<n;i++)



    {



  colForrow[row]=i;



   if(checkValidQueen(row,colForrow))



        helper_queen(n,row+1,colForrow,res);



    }



}//逐行求解，在每一行尝试每个列位置





vector< vector<string> > solveNQueens(int n){




vector< vector<string> >res;




int * colForrow=(int*)malloc(sizeof(int)*n);



helper_queen(n,0,colForrow,res);




return res;



                                             }

以n=4来简单描述思路：

五大经典算法二回溯

再例如39. Combination Sum
给定一候选序列和一个目标值，要求从候选序列中选出若干数据使得它们之和与目标值相等，这里每个选出的数据可以被重复使用。还是回溯思想：

一选择：选择一个元素

二条件：

三直到和与taget相等

设计思路：

也是循环递归方式，每次递归中某次循环i时选择candidate[i]元素，把剩下的元素一一加到结果集合中，并且把目标减去加入的元素，然后把剩下元素（由于可以重复使用故包括当前加入的元素）放到下一层递归中解决子问题。若得到的差值小于0，则失败，需要增加该递归中的循环i，循环结束返回上一层函数，此时需要清空已经放入结果集的元素，该层i自增。若最终得到差值为0则存储结果。





void sift(vector<int>&nums,int low,int high){



    int i=low,j=2*i+1;



    if(low<high){



   int tmp=nums[low];



 while(j<=high){



     if(j+1<=high&&nums[j]<nums[j+1])j++;



       if(nums[j]>tmp){nums[i]=nums[j];i=j;j=2*i+1;}



     else break;



                }



 nums[i]=tmp;



                  }



                                            }




void sort_heap(vector<int>&num){



    int n=num.size();



    for(int i=n/2-1;i>=0;i--)



 sift(num,i,n-1);



    for(int i=n-1;i>=1;i--){int t=num[0];num[0]=num[i];num[i]=t;sift(num,0,i-1);}



    //for(int i=0;i<num.size();i++)cout<<num[i]<<" ";




                                }



//combinationsum




void helper_combination(vector<int> candidates,int start,int target,vector<int> item,vector< vector<int> >&res){




if(target<0)return;




if(target==0){res.push_back(item);return;}//达到结束





for(int i=start;i<candidates.size();i++){



   if(i-1>=0&&candidates[i]==candidates[i-1])continue;//因为可以重复使用，故集合里的重复元素没有什么用




   item.push_back(candidates[i]);



   helper_combination(candidates,i,target-candidates[i],item,res);



   item.pop_back();//这里需要删除




                                     }



                                                                                    }




vector< vector<int> > combinationSum(vector<int>& candidates,int target){



sort_heap(candidates);




vector< vector<int> >res;




vector<int> item;



helper_combination(candidates,0,target,item,res);




return res;



}

举例如下：

候选集合[2,3,6,7]，target=7

正确结果：




[



  [7],



  [2, 2, 3]



]

大概思路：

五大经典算法二回溯

77. Combinations
也类似思路，给出n，从1-n选出k个组成一对，求出所有这样的对

例如

n=4,k=2:




[



  [2,4],



  [3,4],



  [2,3],



  [1,2],



  [1,3],



  [1,4],



]

也是循环递归，不合适回溯上一递归。




/combinations





void helper_combine(int n,int k,int start,vector<int> item,vector< vector<int> >&res){




if(item.size()==k){res.push_back(item);return;}




for(int i=start;i<=n;i++)



{item.push_back(i);



    helper_combine(n,k,i+1,item,res);



 item.pop_back();



}



}




vector< vector<int> >combine(int n,int k){




vector< vector<int> >res;




if(n<1||k>n)return res;




vector<int> item;



helper_combine(n,k,1,item,res);




return res;



}

对于46. Permutations 也一人如此

对于只给出数字n：




//permutation




void helper_Npermutation(int n,int start,vector<int> item){




if(n==item.size()){for(int i=0;i<n;i++)cout<<item[i]<<" ";cout<<endl;}




else{



    for(int i=1;i<=n;i++)



    {   int f=1;



  for(int j=0;j<start;j++) if(item[j]==i)f=0;



        if(f){



   item.push_back(i);



  helper_Npermutation(n,i+1,item);



   item.pop_back();}



    }



     }



}




void getNpermutation(int n){




if(n<1)return;




vector<int>item;



helper_Npermutation(n,0,item);



}

对于给出一个非重复序列：





void helper_permutation(vector<int> candidates,int start,vector<int> item,vector< vector<int> >&res){




if(item.size()==candidates.size()){res.push_back(item);return;}




int n=candidates.size();




for(int i=0;i<n;i++)



{int f=1;



    for(int j=0;j<item.size();j++)if(item[j]==candidates[i])f=0;



 if(f){



     item.push_back(candidates[i]);



     helper_permutation(candidates,i+1,item,res);



     item.pop_back();



       }



}



}




vector< vector<int> > permute(vector<int>& nums){




vector< vector<int> >res;




if(nums.size()<1)return res;




vector<int>item;



helper_permutation(nums,0,item,res);




return res;



}

对于给出一个重复序列：
主要先要排序：





void helper_permutation(vector<int> candidates,int start,vector<int> item,vector< vector<int> >&res){




if(item.size()==candidates.size()){res.push_back(item);return;}




int n=candidates.size();




for(int i=0;i<n;i++)



{   if(!i||candidates[i]!=candidates[i-1]){



    int f1=0,f2=0;



    for(int j=0;j<item.size();j++)if(item[j]==candidates[i])f1++;



    for(int j=0;j<n;j++)if(candidates[j]==candidates[i])f2++;



 if(f2>f1){



     item.push_back(candidates[i]);



     helper_permutation(candidates,i+1,item,res);



     item.pop_back();



       }



}



}



}




vector< vector<int> > permuteUnique(vector<int>& nums){




vector< vector<int> >res;




if(nums.size()<1)return res;




vector<int>item;



sort(nums.begin(),nums.end());//include <algorithm>




helper_permutation(nums,0,item,res);




return res;



}

140. Word Break II





string vectorcharTostring(vector<char> ss){



    string res="";



    for(int i=0;i<ss.size();i++)



  res+=ss[i];



    //res+='\0';




    return res;



                                            }




bool find_vector(vector<string> ss,string s){




int i=0;




while(i<ss.size()){if(s.compare(ss[i])==0)return 1;i++;}




return 0;



}



//word break2




void helper_wordbreak(string s,vector<string> wordDict,int start,string item,vector<string>& res){




if(start>=s.length()){res.push_back(item);item.clear();return;}



    vector<char> t;




for(int i=start;i<s.length();i++)



{



 



    t.push_back(s[i]);



   // cout<<vectorcharTostring(t).size()<<endl;




     if(find_vector(wordDict,vectorcharTostring(t)))



   {



    //item+=(vectorcharTostring(t));




    //if(i<s.length()-1)item+=" ";




    string newitem=item.length()?(item+" "+vectorcharTostring(t)):vectorcharTostring(t);



    helper_wordbreak(s,wordDict,i+1,newitem,res);



    



   }



   



}



}




vector<string> wordBreak(string s, vector<string>& wordDict){




vector<string> res;




if(wordDict.size()<1)return res;




string item="";



helper_wordbreak(s,wordDict,0,item,res);




return res;



}

这种类似以前NQueen，Permutation做法正确，但是会超时Time Limit Exceeded！故需要完善。结合139. Word Break 题采用的动态规划做法，这里也可以引入，故代码修改如下：





bool find_vector(vector<string> ss,string s){




int i=0;




while(i<ss.size()){if(s.compare(ss[i])==0)return 1;i++;}




return 0;



}



//word break2




void helper_wordbreak(string s,vector<string> wordDict,int start,string item,vector<string>& res,vector<bool> dp){



 string t;




for(int i=1;i+start<=s.length();i++)



{



  if(dp[i+start]&&find_vector(wordDict,s.substr(start,i))){



      t=s.substr(start,i);



      if(i+start<s.length())helper_wordbreak(s,wordDict,i+start,item+t+" ",res,dp);



      else res.push_back(item+t);



                                                           }



}



}




vector<string> wordBreak(string s, vector<string>& wordDict){




vector<string> res;




if(wordDict.size()<1)return res;




string item="";




vector<bool> dp(s.length()+1,false);



dp[0]=true;




int min_len=INT_MAX,max_len=0;




for(int i=0;i<wordDict.size();i++){if(min_len>wordDict[i].size())min_len=wordDict[i].size();



                   if(max_len<wordDict[i].size())max_len=wordDict[i].size();



                 }



 




for(int i=0;i<s.size();i++){




if(dp[i]){for(int len=min_len;i+len<=s.size()&&len<=max_len;len++)



       if(find_vector(wordDict,s.substr(i,len)))dp[i+len]=1;



     }



             }




if(dp[s.length()])



helper_wordbreak(s,wordDict,0,item,res,dp);




return res;



}

131. Palindrome Partitioning

给定一个字符串，把内部分部，使得每部分子串也是回文串。

首先需要得到字符串所有字串是否是回文，这里采用动态递归法，引入二维数组bool dp[i][j]，表示从i到j这一子串是否是回文，下面是递归公式

dp[i][j]=1 when s[i]==s[j]&&j-i==1(即相邻)或者dp[i+1][j-1]=1

dp[i][j]=0;

故初始值为0。





vector <vector <bool> > getdict(string s){




vector< vector<bool> > res;




for(int i=0;i<s.length();i++){



    vector<bool> aa;



    for(int j=0;j<s.length();j++){aa.push_back(0);};



    res.push_back(aa);



                              }




if(s.size()<1)return res;




for(int i=s.length()-1;i>=0;i--)



    for(int j=i;j<s.length();j++)



 if(s[i]==s[j]&&((j-i<2)||res[i+1][j-1]))res[i][j]=1;



 




return res;



                                          } //判断任意字串之间是不是回文

剩下的很明显也是循环递归，不合适回溯即可：




//palindrome Partitioning




vector <vector <bool> > getdict(string s){




vector< vector<bool> > res;




for(int i=0;i<s.length();i++){



    vector<bool> aa;



    for(int j=0;j<s.length();j++){aa.push_back(0);};



    res.push_back(aa);



                              }




if(s.size()<1)return res;




for(int i=s.length()-1;i>=0;i--)



    for(int j=i;j<s.length();j++)



 if(s[i]==s[j]&&((j-i<2)||res[i+1][j-1]))res[i][j]=1;



 




return res;



                                          } //判断任意字串之间是不是回文





void helper_partitioning(string s,vector< vector<bool> > dict,int start, vector<string> item,vector< vector<string> > &res){




if(start==s.length()){res.push_back(item);return;}




for(int i=start;i<s.length();i++)



{if(dict[start][i]){item.push_back(s.substr(start,(i-start+1)));helper_partitioning(s,dict,i+1,item,res);item.pop_back();}



}



}




vector< vector<string> > partition(string s){




vector< vector<string> >res;




if(s.length()<1)return res;




vector< vector<bool> >dict;



dict=getdict(s);




vector<string> item;



helper_partitioning(s,dict,0,item,res);




return res;



}

93. Restore IP Addresses

给定一个只含数字的字符串，判断所能得到的所有IP地址

例如：

s=”25525511135”

则存在[“255.255.11.135”, “255.255.111.35”]

首先判断IP地址要求的格式：

1 一定含有点分开的四段子字段，每段字符数最多3个

2 每个子字段转换成int范围是0-255

3 每个字符串可以是0，但不能是00，01，0XX

同样运用回溯，次取1，2，3长度的子串，判断其为合法的IP地址子字段后，取后面的真个字符串递归判断，通过count从0增加到3来判断是否完成4个子段的判断，将结果加入最终的res中去。





bool isValidsubstr(string substr1){




if(substr1[0]=='0'){return substr1=="0";



                   }




int res=atoi(substr1.c_str());




return res>=0&&res<=255;



}//判断字串合法





void helper_ipaddress(string s,int start,string item,vector<string>&res){




if(start==3&&isValidsubstr(s)){res.push_back(item+s);return;}




for(int i=1;i<=3&&i<s.size();i++){



    string sub=s.substr(0,i);



    if(isValidsubstr(sub)){helper_ipaddress(s.substr(i),start+1,item+sub+".",res);}



                             }



}




vector<string> restoreIpAddresses(string s){




vector<string> res;




if(s.size()<1||s.size()<4||s.size()>12)return res;




string item="";



helper_ipaddress(s,0,item,res);




return res;



}

转自博文：五大经典算法二回溯

五大经典算法二回溯