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

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

class Solution {
public:
    /**
     * @param s: A string
     * @return: A list of lists of string
     */
     
    void helper(vector<vector<string> > & ret, string s, vector<string> tmp) {
        if(s.size() == 0) {
            ret.push_back(tmp);
            return;
        }
        
        for(int i = 1; i <= s.size(); ++i) {
            string str = s.substr(0, i);
            //cout << str << endl;
            if(check(str)) {
                tmp.push_back(str);
                helper(ret, s.substr(i), tmp);
                tmp.pop_back();
            }
            
        }
    }
    
    bool check(string str) {
        if(str.size() == 0 || str.size() == 1) {
            return true;
        }
        int len = str.size();
        for(int i = 0; i <= len/2 - 1; ++i ) {
            if(str[i] != str[len-1-i]) {
                return false;
            }
        }
        
        return true;
    }
     
    vector<vector<string>> partition(string s) {
        // write your code here
        
        vector<vector<string> > ret;
        vector<string> tmp;
        helper(ret, s, tmp);
        
        return ret;
        
    }
};