39. 组合总和
回溯三部曲：
定义两个全局变量，二维数组result存放结果集，数组path存放符合条件的结果
首先是题目中给出的参数，集合candidates, 和目标值target。用startIndex来控制for循环的起始位置
递归终止条件
sum大于target和sum等于target
单层搜索的逻辑
单层for循环依然是从startIndex开始，搜索candidates集合
for(inti=startIndex;i<candidates.size();i++){sum+=candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,sum,i);// 关键点:不用i+1了，表示可以重复读取当前的数sum-=candidates[i];// 回溯path.pop_back();// 回溯}
40.组合总和II
这道题比上一题多了个去重的操作
去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重
回溯三部曲
递归函数参数
加一个bool型数组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.分割回文串
回溯三部曲
递归函数参数
全局变量数组path存放切割后回文的子串，二维数组result存放结果集。 （这两个参数可以放到函数参数里）
本题递归函数参数还需要startIndex，因为切割过的地方，不能重复切割，和组合问题也是保持一致的
递归函数终止条件
切割线切到了字符串最后面，说明找到了一种切割方法，此时就是本层递归的终止条件
传入startIndex，表示下一轮递归遍历的起始位置，这个startIndex就是切割线
单层搜索的逻辑
在for (int i = startIndex; i < s.size(); i++)循环中，我们 定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。
首先判断这个子串是不是回文，如果是回文，就加入在vector<string> path中，path用来记录切割过的回文子串
切割过的位置，不能重复切割，所以，backtracking(s, i + 1); 传入下一层的起始位置为i + 1
这里还引入动归思想，厉害了
网友评论