回溯算法(C/C++)

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法。
回溯算法类似于枚举的过程，当搜索时遇到不满足条件，回退到上一个，尝试别的路径。
回溯是递归的产物，有递归一定有回溯。

回溯算法并不是什么高效的算法，因为本质上时去遍历所有元素，找出所有可能，然后选出需要的答案。那为什么还要回溯法，简单来说，不是所有的问题都能用什么巧妙的方法来解决的，有些问题你能暴力求解出来就不错了。

这里是综合了一下参考的别人写的，有这么几种情况适合回溯法解决：

回溯法使用多了不难发现，回溯法的问题都可以抽象转换为树型结构，你可以画一棵树来分析这类问题，因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。因为递归就要有终止条件，所以必然是一颗高度有限的树（N叉树）。

for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历

有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 . 分隔。例如： 0.1.2.201 和 192.168.1.1 是 有效的 IP 地址，但是 0.011.255.245 、 192.168.1.312 和 192.168@1.1 是 无效的 IP 地址。
问题想到用for可以解，但是这要多少层for啊，我们试一下回溯的方法。
1.首先确定参数
全局变量数组path存放切割后回文的子串，二维数组result存放结果集。本题递归函数参数还需要startIndex，因为切割过的地方，不能重复切割，和组合问题也是保持一致的。如果是一个集合来求组合的话，就需要startIndex，startIndex来控制for循环的起始位置。

2.递归终止条件
本题明确要求只会分成4段，所以用分割的段数作为终止条件。pointNum表示点的数量，pointNum为3说明字符串分成了4段了。然后验证一下第四段是否合法，如果合法就加入到结果集里。

3.单层搜索的逻辑
在for (int i = startIndex; i < s.size(); i++)循环中 [startIndex, i]这个区间就是截取的子串，需要判断这个子串是否合法。
如果合法就在字符串后面加上符号.表示已经分割。
如果不合法就结束本层循环，剪掉此分支。

然后就是递归和回溯的过程，递归调用时，下一层递归的startIndex要从i+2开始（因为需要在字符串中加入了分隔符.），同时记录分割符的数量pointNum 要 +1。回溯的时候，就将刚刚加入的分隔符. 删掉就可以了，pointNum也要-1。

文章参考： https://mp.weixin.qq.com/s/gjSgJbNbd1eAA5WkA-HeWw
https://mp.weixin.qq.com/s/v--VmA8tp9vs4bXCqHhBuA
https://www.jianshu.com/p/4abfd96d91e6