class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        if (s.empty()) {
            return res;
        }
        vector<string> path;
        int index = 0;
        backTrace(s, index, path, res);
        return res;
    }
    
    void backTrace(const string& s, int index, vector<string>& path, vector<vector<string>>& res) {
        if (index == s.size()) {
            res.push_back(path);
            return;
        }
        for (int i = index; i < s.size(); ++i) {
            if (isPalindrome(s, index, i)) {
                path.push_back(s.substr(index, i-index+1));
                backTrace(s, i+1, path, res);
                path.pop_back();
            }
        }
    }
    
    bool isPalindrome(const string& s, int left, int right) {
        while (left < right) {
            if (s[left++] != s[right--]) {
                return false;
            }
        }
        return true;
    }
};