39.?組合總和

回溯三部曲：

定義兩個全局變量，二維數(shù)組result存放結果集，數(shù)組path存放符合條件的結果

首先是題目中給出的參數(shù)，集合candidates, 和目標值target。用startIndex來控制for循環(huán)的起始位置

遞歸終止條件

sum大于target和sum等于target

單層搜索的邏輯

單層for循環(huán)依然是從startIndex開始，搜索candidates集合

for(inti=startIndex;i<candidates.size();i++){sum+=candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,sum,i);// 關鍵點:不用i+1了，表示可以重復讀取當前的數(shù)sum-=candidates[i];// 回溯path.pop_back();// 回溯}

40.組合總和II

這道題比上一題多了個去重的操作

去重的是同一樹層上的“使用過”，同一樹枝上的都是一個組合里的元素，不用去重

回溯三部曲

遞歸函數(shù)參數(shù)

加一個bool型數(shù)組used，用來記錄同一樹枝上的元素是否使用過。

這個集合去重的重任就是used來完成的。

遞歸終止條件

終止條件為?sum > target?和?sum == target

單層搜索的邏輯

used[i - 1] == true，說明同一樹枝candidates[i - 1]使用過

used[i - 1] == false，說明同一樹層candidates[i - 1]使用過

這里?used[i - 1] == false說明當前取的 candidates[i] 是從 candidates[i - 1] 回溯而來的

131.分割回文串

回溯三部曲

遞歸函數(shù)參數(shù)

全局變量數(shù)組path存放切割后回文的子串，二維數(shù)組result存放結果集。 （這兩個參數(shù)可以放到函數(shù)參數(shù)里）

本題遞歸函數(shù)參數(shù)還需要startIndex，因為切割過的地方，不能重復切割，和組合問題也是保持一致的

遞歸函數(shù)終止條件

切割線切到了字符串最后面，說明找到了一種切割方法，此時就是本層遞歸的終止條件

傳入startIndex，表示下一輪遞歸遍歷的起始位置，這個startIndex就是切割線

單層搜索的邏輯

在for (int i = startIndex; i < s.size(); i++)循環(huán)中，我們 定義了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。

首先判斷這個子串是不是回文，如果是回文，就加入在vector<string> path中，path用來記錄切割過的回文子串

切割過的位置，不能重復切割，所以，backtracking(s, i + 1); 傳入下一層的起始位置為i + 1

這里還引入動歸思想，厲害了