回溯法：彻头彻尾的理解回溯算法
一、拆分回文串
求解多个结果，用DFS
属于对一维数组进行DFS搜索。
典型的DFS应用题。代码格式跟DFS实战中的N-Queens问题一样。
需要三个函数，isvalid函数，用来判断是否是有效回文。recur函数，对子问题进行递归。main函数，调用递归函数。
DFS+ 回溯法。
DFS——怎么深搜下去
类似于N-Queens方法中的，从第一行开始，为皇后找到正确位置以后，就对剩下的行进行递归。
这里把问题切分成可以递归的子问题：从第一个字母开始，逐个与后面的字母进行组合，如果组合是回文，那么就把后面剩下的字符串都传入递归函数中。
比如，一开始把aabc传入递归函数中
1、第一个字母a是回文，那么就把abc再传入递归函数2中。对于abc，第一个 字母是a，就这样把bc传入递归函数3中 ，直到把c传入递归函数4。
2、在以abc为参数的递归函数2结束调用以后，此时，从第一个字母a与后面的字母进行组合，发现aa也是回文，于是把剩下的bc传入递归函数2中。
3、接着判断第一个字母a与后面两个字母的组合，aab，发现不是回文，那么这个结果就不正确，再进行组合，把aabc判断，发现也不是，于是递归函数2的所有调用就结束了。
回溯法——递归完以后，怎么返回上一个递归函数
for (int i = start; i < s.size(); ++i) {
if (isPalindrome(s, start, i)) {
out.push_back(s.substr(start, i - start + 1));
partitionDFS(s, i + 1, out, res);
out.pop_back();
s.substr(start, i - start + 1)中，第一个参数start是起始位置，i - start +1 是接下来切片的长度。
以上面aabc为例，在得到out = a,b,c,d这个结果以后，递归函数4结束。在递归函数3中，out弹出c，此时start等于3，再把i加1以后，等于4，结束循环，于是递归函数2的调用也结束了。此时再递归函数1中，out弹出b。
然后由于递归函数1中的i一开始等于start=2，于是i+1 = 3，然后判读bc是不是回文。。。
那么，对原字符串的所有子字符串的访问顺序是什么呢，如果原字符串是 abcd, 那么访问顺序为: a -> b -> c -> d -> cd -> bc -> bcd-> ab -> abc -> abcd, 这是对于没有两个或两个以上子回文串的情况。那么假如原字符串是 aabc，那么访问顺序为：a -> a -> b -> c -> bc -> ab -> abc -> aa -> b -> c -> bc -> aab -> aabc，中间当检测到aa时候，发现是回文串，那么对于剩下的bc当做一个新串来检测，于是有 b -> c -> bc，这样扫描了所有情况，即可得出最终答案。
大致情况就是这样，跟八皇后一样，都是DFS+回溯法，最重要的就是，分析好问题，怎么去寻找下一个子问题，以及怎么回溯回来。
大致问题，跟树的前序遍历一样。
二、组合数的和
这题看LeetCode66题总结上的代码，比较简洁些。
[LeetCode] Combination Sum 组合之和
题目跟上一题的套路还是一样一样的：在递归函数1中，从传入的数组的第一个元素开始，对满足条件的点再次进行递归函数调用2，然后在第一个元素情况下，递归函数2执行完毕以后 ，弹出out中的元素。
再在递归函数1中，从第二个元素开始，对满足条件的点进行递归调用2.。。
套路是一样的，但是还是有一点不一样，因为这个问题中，允许结果有重复的元素存在。比如，nums = [2,3,6,7],target = 7,那么[2,2,3]也是一个有效解。
一开始我以为，要是按照上面几题思路的话，如果在递归函数中，再次调用递归函数传入的 i 不加1的话，会陷入死循环了。如果是 i + 1的话，就没办法传入相同的元素了。
其实不然，这里在递归调用时，相比于上面的递归函数中有四个参数（原一维数组，i，out，res），这里还要多一个gap。因此每次传入相同的i时，还会传入一个改变的gap = gap - nums[i]，然后再加一个判断条件用来剪枝即可。比如，一开始递归函数1传入gap=7，i=0,递归函数2传入gap = 7-2=5,i=0,递归函数3传入gap=3，i=0,，out此时为[2,2,2]，递归函数4传入gap=1，i=0，然后发现gap<nums[0]，于是就return，返回递归函数3，pop出 2，然后在for循环中，i +1 = 1，此时再次传入 到递归函数4中，发现符合条件。
即，如果有相同元素的话，需要在递归函数中，传入变化的条件保证递归能够结束，传入相同的 i 保证能够用到相同的元素、
网友评论