切割问题其实是一个组合问题！分割回文字符串题目链接：https://leetcode-cn.com/problems/palindrome-partitioning/给定一个字符串s，将s分成一些子串string，使得每个子串都是一个回文。返回s所有可能的分裂方案。例子：输入："aab"输出：[["aa","b"],["a","a","b"]]思路这道题涉及两个关键问题：切题，有不同的判断palindromebythecuttingmethod相信这里不同的切法会让很多同学感到迷惑。这种题如果想用for循环暴力解决可能就没那么容易写了，所以需要换一种暴力的方式，也就是回溯。可能有的同学想不通回溯是怎么切字符串的？我们来分析一下切割。事实上，切割问题类似于组合问题。例如对于字符串abcdef：组合题：选择a后，选择bcdef中的第二段，选择b后，选择cdef中的第三段...切割问题：切割a后，切割bcdef中的第二段，然后切b，切cdef中的第三段……有感觉吗？所以切割问题也可以抽象成一个树结构，如图：递归拆分回文串进行垂直遍历，for循环进行水平遍历，切割线（图中红线）切割到结束位置的字符串，说明找到了切割方法。至此可以发现，切割问题的回溯搜索过程与组合问题的回溯搜索过程类似。回溯三部曲递归函数参数的全局变量数组path存放切回文的子串，二维数组result存放结果集。（这两个参数可以放在函数参数里面。）这题递归函数参数也需要startIndex，因为切的地方不能重复切，也和组合题一致。在39.Combinatorialsums中，我们深入探讨了组合问题何时需要startIndex以及何时不需要。代码如下：vector>result;vectorpath;//放入回文子串voidbacktracking(conststring&s,intstartIndex){递归函数终止条件从树结构图中拆分出回文串即可可以看到切割线切割到字符串的末尾，说明找到了切割方法，这就是本层递归的终止条件。那么代码中的切割线是什么呢？在处理组合问题时，需要在startIndex中传入recursive参数，表示下一轮递归遍历的起始位置。这个startIndex就是切割线。所以终止条件代码如下：voidbacktracking(conststring&s,intstartIndex){//如果起始位置大于s的大小，说明已经找到一组切分方案if(startIndex>=s.size()){result.push_back(path);return;}}单级查找逻辑下面看看递归循环中如何截取子串？在for(inti=startIndex;i=s.size()){result.push_back(path);return;}for(inti=startIndex;i>partition(strings){result.clear();path.clear();backtracking(s,0);returnresult;}};Leetcode是中等的，但是可以说是hardtopic，但是按照模板看代码居然这么难。有什么困难？我列出以下难点：切割问题可以抽象为组合问题。如何模拟那些切线切割问题中如何终止递归，如何在递归循环中截取子串，如何判断回文我们平时做难题的时候，也是需要训练的能力，弄清楚在哪里困难在于。有的同学可能会遇到难的题，但是不知道题难在哪里。总之，他们很难。其实思路还是不够清晰。这种总结能力需要多接触多锻炼。对于这道题，相信很多同学主要卡在了第一个难点上：就是不知道怎么切，甚至不知道回溯法怎么用，但是就是不知道怎么用。也就是说，我没有意识到切割可以按照组合题的套路来解决。如果你意识到这一点，那就是一个重大的突破。接下来就可以根据模板画一个葫芦了。但是如何模拟切割线，如何终止，如何截取子串，其实是很难想的。最后，判断回文是最简单的。关于模拟切割线，其实index就是上一层已经确定的分界线，i就是这一层要找的新的分界线。除了这些难点之外，这道题还有一些细节，比如：切的地方不能重复切，所以递归的函数需要传入i+1。所以这个题应该是一道难题。可能刷过这道题的记录者并没有觉得自己克服了那么多困难，所以才把这道题当成AC。本文转载自微信公众号《代码随想录》，可通过以下二维码关注。转载本文请联系CodeCaprice公众号。
