39. 組合總和
思路：
變量：
全局變量：
vector<vector<int>>?result; vector<int>path夕冲；int?sum=0;
函數(shù)變量：
vector<int>&candidates,int?target,?int?startIndex
終止條件：
sum==target時將path放進(jìn)result;
單層邏輯：
for(int?i=startIndex;i<candidates.size();i++)
sum+=;path.push();backtracking(candidates,target,i);path.pop();sum-=;
注意：本題可以重復(fù)選取元素，因此單層內(nèi)的嵌套回溯i不需要i+1裂逐；
剪枝：
if(sum>target) return;
看視頻后：
和視頻思路相同歹鱼。
40.組合總和II
思路：
按照上一題進(jìn)星類似思路，可以取相同值卜高，因此單層搜索中i弥姻；但是由于有重復(fù)元素，不知道如何進(jìn)行去重
看視頻后：
組合問題可以抽象為樹形結(jié)構(gòu)掺涛，那么“使用過”在這個樹形結(jié)構(gòu)上是有兩個維度的蚁阳，一個維度是同一樹枝上使用過，一個維度是同一樹層上使用過鸽照。我們要去重的是同一樹層上的“使用過”螺捐，同一樹枝上的都是一個組合里的元素，不用去重矮燎。樹層去重的話定血，需要對數(shù)組排序！
因此涉及去重的操作為
1. sort排序數(shù)組
2.增加一個bool的數(shù)組記錄取元素的情況诞外，并用以下判斷
?if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==false){continue;}
剪枝：sum>target
131.分割回文串
思路：
無澜沟。
看視頻后：
1. 寫一個判斷回文子串的函數(shù)
2. backtracking
變量：
全局：result，path
函數(shù)變量：string s,int starti;
終止條件：
if(starti==s.size()) //starti為切割的線
單層循環(huán)：
for(int?i=starti;i<s.size();i++)
????????{
??????????? if(rv(s,starti,i))//判斷是否為回文子串
????????????{
????????????????string?str=s.substr(starti,i-starti+1);//記錄子串峡谊，范圍是starti-i茫虽，切割范圍
????????????????path.push_back(str);
????????????}
????????????else?
????????????????continue;//不是子串就跳過
????????????backtracking(s,i+1);
????????????path.pop_back();
????????}
切割其實(shí)是一種組合問題刊苍，重要的是切割線和切割范圍。注意切割過的位置濒析，不能重復(fù)切割正什，所以，backtracking(s, i + 1); 傳入下一層的起始位置為i + 1号杏。
本題難點(diǎn)：
切割問題可以抽象為組合問題
如何模擬那些切割線
切割問題中遞歸如何終止
在遞歸循環(huán)中如何截取子串
如何判斷回文
