文章目錄

• 五：括號生成問題
• 六：組合總和（點擊跳轉）
• 七：子集問題（點擊跳轉）

五：括號生成問題

這個問題也比較經典，題目的要求是讓你生成所有可能的并且 有效的 括號組合。

對于括號問題，兩個特性，請你一定記牢

一個合法的括號左括號數量一定等于右括號的數量

從左往右數一定是左括號先多，也就是不能先出現右括號

根據回溯算法的思路，本題給出了n，那么對于其每一種可能就有2*n個位置，也就是這道題就轉化為了每個位置如何放置括號可以滿足括號組合是合法的這樣的問題

那么很顯然，我們可以暴力窮舉所有可能的組合，然后再從其中剔除掉不可能的組合即可。這里我們可以這樣做，分別用left和right記錄左右括號的數量，放置一個左括號，那么left就減一，放置一個右括號那么right就減一。

class Solution { public:vector<string> ret;vector<string> generateParenthesis(int n) {if(n==0)//特判{return ret;}string track;//一個組合back(track,n,n);return ret;}void back(string& track,int left,int right){//從左往右一定是左括號多if(left>right)return;if(left<0 || right<0)//如果括號數大于3個，那么就結束遞歸，然后跑到pop_back處，刪掉多余的括號return;//所有括號恰好用完時，滿足if(left==0 && right==0){ret.push_back(track);return;}//放左括號track.push_back('(');back(track,left-1,right);track.pop_back();//放右括號track.push_back(')');back(track,left,right-1);track.pop_back();} };

class Solution { public:vector<vector<int>> ret;vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<int> track;back(candidates,track,target);return ret;}void back(vector<int>& candidates,vector<int>& track,int target){// sort(track.begin(),track.end());// if(ret.size()!=0)// {// for(int i=0;i<ret.size();i++)// {// if(ret[i]==track)// return;// }// }int sum=accumulate(track.begin(),track.end(),0);if(sum==target){ret.push_back(track);return;}if(sum>target)return;for(int i=0;i<candidates.size();i++){track.push_back(candidates[i]);back(candidates,track,target);track.pop_back();}} };

六：組合總和（點擊跳轉）

這個問題要我們找出數組中可以加和生成目標數的數字，一個數字可以無限次選取。基本框架不用多說，這里需要注意，如果只把框架寫出來，它生成的這些數字是滿足題意的，但是有一部分會重復，所以我們在把一個組合假如到返回結果之前，需要判斷一下這個待加入的組合是否之前出現過，所以為了減少回溯次數，在開始就要將原數組排序好

class Solution { public:vector<vector<int>> ret;//返回結果vector<vector<int>> combinationSum(vector<int>& candidates, int target) {sort(candidates.begin(),candidates.end());//為了減少回溯次數，先排好序vector<int> track;//用于保存一個滿足題意的組合back(candidates,track,target);return ret;}void back(vector<int>& candidates,vector<int>& track,int target){int sum=accumulate(track.begin(),track.end(),0);//每次進入時，利用accumulate函數計算這個組合的數字之和是否達到了要求if(sum==target)//如果等于目標值，表明達到了要求{vector<int> judge(track);sort(judge.begin(),judge.end());//但是我們需要判斷此時滿足調節的這個組合之前是否出現過，所以要排好序進行判斷（因為首先出現的那些情況一定是基準，是有序的）if(ret.size()!=0){for(int i=0;i<ret.size();i++){if(ret[i]==judge)//一旦出現重復，不準加入return;}}ret.push_back(track);//不重復的話，就作為一種選擇加入return;}if(sum>target)//如果大于，直接不滿足return;for(int i=0;i<candidates.size();i++){track.push_back(candidates[i]);//做選擇back(candidates,track,target);//回溯track.pop_back();//撤銷選擇}} };

七：子集問題（點擊跳轉）

這道題比較有意思，因為他的決策樹不是特別好找，關鍵就在于發現規律。
舉個例子[1,2]的所有子集為：【[],[1],[2],[1,2]】，而[1,2,3]的子集為：【[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]】，大家有沒有發現123的子集就是12的子集追加3，那么12的子集就是1的子集追加2，同時1的子集就是空集追加1，，因此其決策樹為

class Solution { public:vector<vector<int>> ret;vector<vector<int>> subsets(vector<int>& nums) {vector<int> track;back(nums,track,0);return ret;}void back(vector<int>& nums,vector<int>& track,int start)//注意start這個變量{ret.push_back(track);for(int i=start;i<nums.size();i++)//123的子集等12的子集追加3，12的子集等于1的子集追加2,1的子集等于空集追加1{track.push_back(nums[i]);back(nums,track,i+1);track.pop_back();}} };

總結

以上是生活随笔為你收集整理的回溯算法详解：理论+基础类回溯题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。