131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

class Solution {
public:
    vector>res;
    vector path;
    //判断回文，easy
    bool isprime(string s,int left,int right){
        while(left < right){
            if(s[left] != s[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
 
    void backtracking(string& s,int startindex){
        //终止条件，也容易判断出来
        if(startindex >= s.size()){
            res.push_back(path);
            return;
        }
 
        for(int i = startindex;i < s.size();i++){
            //aaab
            //难点：每次切割的字符串怎么得出边界
            //2、如何模拟切割线，其实就是i和startindex
            //startindex是上一层的给下一层(本层)的起始点，而i是本层的，一直遍历本层之后的元素，如果本层从第二个a开始，i从第二个2开始遍历，判断下标(1,1)a,(1,2)aa,(1,3)aab是否是回文，如果是，就向深层递归。
            //然后继续 本层 变为上一层，向下开拓一层，判断下标(2,2)a,(2,3)ab。以此类推。
            if(isprime(s,startindex,i)){
                string str;
                for(int j = startindex;j <= i;j++){
                    str += s[j];
                }
                path.push_back(str);
            }
            //不是回文，那直接跳过，i++看本层之后的的元素。
            else{
                continue;
            }
            backtracking(s,i+1);
            path.pop_back();
        }
    }
    vector> partition(string s) {
        backtracking(s,0);
        return res;
    }
};