Leetcode 39. 組合總和

題目鏈接?39 組合總和

本題目和前面的組合問題差不多，只不過這里能重復選取數字，還是要注意組合的定義，交換數字順序還是算一個組合，所以這里還是用我們的startIndex來記錄取的數字到哪里了，下面上代碼：

class Solution {private:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& candidates, int target,int sum,int startIndex){if(sum>target){return ;}if(sum==target){result.push_back(path);return ;}for(int i=startIndex;i<candidates.size()&&sum+candidates[i]<=target;i++){//其實如果已經知道下一層的sum會大于target，就沒有必要進入下一層遞歸了。//對總集合排序之后，如果下一層的sum（就是本層的 sum + candidates[i]）已經大于target，就可以結束本輪for循環的遍歷。path.push_back(candidates[i]);sum+=candidates[i];backtracking(candidates, target,sum,i);// 不用i+1了，表示可以重復讀取當前的數sum-=candidates[i];path.pop_back();}}
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());//從小到大排序
backtracking(candidates, target,0,0);return result;}
};

Leetcode 40. 組合總和 II

題目鏈接?40 組合總和 II

本題目的要求是每個集合的元素只能出現一次，所以說我們需要去重，如何去重才是本題目的關鍵，其他的地方和上面的題目一樣，我們將回溯函數轉化為樹狀圖，其實可以分為兩個去重，一個是樹枝去重，一個是樹層去重，下面用一個圖片來體現如何去重：

（默認sort排序）在樹枝上的去重我們已經完成，我們再看在樹層上，取第二個1的時候下面的情況1，2，已經在取第一個1時下面的情況中涉及到了，因為，第一個1后面既有重復的第二個1，也有第二個1后面的元素，所以第一種1一定會包含第二種1的情況。去重我們就完成了，下面直接上代碼：

class Solution {private:vector<int> path;vector<vector<int>> result;void backtracking (vector<int>& candidates,int target,int sum,int startIndex,vector<bool>& used){if(sum==target){result.push_back(path);return ;}for(int i=startIndex;i<candidates.size()&&sum+candidates[i]<=target;i++){// used[i - 1] == true，說明同一樹枝candidates[i - 1]使用過// used[i - 1] == false，說明同一樹層candidates[i - 1]使用過// 要對同一樹層使用過的元素進行跳過if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==false){continue;}path.push_back(candidates[i]);used[i] = true;sum+=candidates[i];backtracking(candidates,target,sum,i+1,used);sum-=candidates[i];used[i] = false;path.pop_back();}}
public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<bool> used(candidates.size(),false);初始化sort(candidates.begin(),candidates.end());backtracking(candidates,target,0,0,used);return result;}
};

Leetcode131. 分割回文串

題目鏈接?131 分割回文串

上面的題目都是組合類的，從這個題目開始就進入分割類題目了，其實組合和分割是一個意思，同樣能用樹狀結構來解決。

除此之外還有幾個需要注意的點，第一個就是將子字符串傳遞給path，用到了substr （s.substr(pos, len)，pos默認值為0，len的默認值是s.size() - pos）轉化字符串，第二個就是回文字符串的判斷，最后就是回溯函數的模板了，上代碼：

class Solution {private:vector<string> path;vector<vector<string>> result;void backtracking (const string& s,int startIndex){if(startIndex>=s.size()){result.push_back(path);return ;}for(int i=startIndex;i<s.size();i++){if(isPalindrome(s,startIndex,i)){string str = s.substr(startIndex,i-startIndex+1);//轉化子字符串path.push_back(str);}else{continue;}backtracking(s,i+1);//遞歸path.pop_back();//回溯}}bool isPalindrome(const string & s,int start,int end){for(int i=start,j=end;i<j;i++,j--){if(s[i]!=s[j]){return false;}}return true;}
public:vector<vector<string>> partition(string s) {backtracking(s,0);return result;}
};

end，狀態不佳啊