有没有觉得这道题很眼熟？前几天刚刚做过 [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。