有没有觉得这道题很眼熟？前几天刚刚做过 [83. N-Queens](../83. N-Queens)。
两者有何区别吗？ N-Queens 是从棋盘第一行开始，深搜试错然后回溯。这个呢，划分点始于字符串开头，依旧是深搜，只不过是遇到对的，就记录。
DFS 都是两者的核心算法。
下面以 "aaba" 为例：
aaba
|
-------------
| |
a|aba aa|ba
^^^ ^^
| |
------- ---
| | | |
a|ba aba b a
^^
|
---
| |
b a
// 结论：
// a a b a
// a aba
// aa b a这样的步骤分解，可以很清楚的看到，每一次分割字符串，都需要深搜到底，才能断定这样的分割是否能够得到我们想要的结果。难度略低于 N-Queens，毕竟没有非常明显的回溯过程。
解决方案的代码结构也与 N-Queens 类似，isPalindrome 判断是否为回文字符串，递归版的 partition 函数，本质就是个 DFS。