131_partition.txt

class Solution {
private:
    vector<vector<string>> res;
    vector<string> path;
public:
    //回溯法
    void backtrace(const string&str,int startindex){
        if(startindex >= str.size()){
            res.push_back(path);
            return;
        }
        for(int i = startindex;i<str.size();i++){
            //判断当前分割的是否是回文串
            if(ispalindrome(str,startindex,i)){
                path.push_back(str.substr(startindex,i-startindex+1));
                // 寻找i+1为起始位置的子串
                backtrace(str,i+1);
                path.pop_back();//回溯弹出这一次的字串
            }
        }
    }
    //判断是否是回文串
    bool ispalindrome(const string& s,int start,int end){
        for(int i = start,j = end;i<j;i++,j--){
            if(s[i]!=s[j])
                return false;
        }
        return true;
    }
    vector<vector<string>> partition(string s) {
        backtrace(s,0);
        return res;
    }
};