难度中等1415
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]示例 2：
输入：s = "a"
输出：[["a"]]提示：
1 <= s.length <= 16s仅由小写英文字母组成
解题思路：回溯
这道题和我们之前讲的组合题不太一样，因为我们现在的关注点是在如何分割这个串上面，所以可以认为现在关注的是两个字符中间是否需要隔开，而不是像组合问题那样子关注每一个元素，这样子的话会更加有利于帮助我们理解该题！
例如对于字符串abcdef：
- 组合问题：选取一个a之后，在 bcdef 中再去选取第二个，选取 b 之后在 cdef 中再选取第三个.....。
- 切割问题：切割一个a之后， 在bcdef 中再去切割第二段，切割 b 之后在 cdef 中再切割第三段.....。
感受出来了不？只是我们对于组合问题关注的是元素，而切割问题我们关心的是元素之间的分割，但是道理都是一样的！递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。说到底，就是这道题关注点是切割线！
所以切割问题，也可以抽象为一棵树形结构，如图：
实现的细节其实和组合问题是一样的，不过注意切割过的位置，不能重复切割，所以，backtracking(s, i + 1); 传入下一层的起始位置为i + 1。
class Solution {
public:
// 判断是否回文的函数
bool isPalindrome(const string& str, int left, int right)
{
while(left < right)
{
if(str[left] != str[right])
return false;
left++;
right--;
}
return true;
}
void backtracking(const string& s, int index)
{
// 递归终止条件：index出界
if(index >= s.size())
{
vv.push_back(v);
return;
}
for(int i = index; i < s.size(); ++i)
{
// 处理：判断是否回文，是的话则加入到v，不是的话直接continue进行剪枝
if(isPalindrome(s, index, i))
v.push_back(s.substr(index, i - index + 1));
else
continue;
backtracking(s, i + 1); // 递归
v.pop_back(); // 回溯
}
}
vector<vector<string>> partition(string s) {
backtracking(s, 0);
return vv;
}
private:
string tmp;
vector<string> v;
vector<vector<string>> vv;
};