回溯二：分割回文串

题目地址： https://leetcode-cn.com/problems/palindrome-partitioning/

题目描述： 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例: 输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]

参考代码：

class Solution {
    vector<vector<string>> result;
    vector<string> single;
    void backtracing(string &s,int startIndex, vector<string> path) {
        // 结束
        if (startIndex >= s.size()) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i<s.size(); i++) {
           string temp =  s.substr(startIndex,i-startIndex+1);
            if (isValid(temp)) {
                path.push_back(temp);
                backtracing(s, i+1,path);
                path.pop_back();
            } else {
                continue; // 之前写的 break ，废物
            }
        }
    }
    bool isValid(string s) {
        for (int i = 0; i<s.size() / 2; i++) {
            if (s[i] != s[s.size()-i-1]) {
                return  false;
            }
        }
        return true;
    }
public:
    vector<vector<string>> partition(string s) {
        result.clear();
        single.clear();
        backtracing(s, 0, single);
        return result;
    }
};

参考链接： https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.md