# Leetcode 131. Palindrome Partitioning
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/palindrome-partitioning/ 。

想法 : 回溯法，複習字串切割語法。

時間複雜度 : O(n * 2^n)。

程式碼 :

class Solution {
public:
    string str;
    vector<vector<string>> ans;
    
    bool isPalindrome(int start, int end){
        for(; start < end ;){
            if(str[start] != str[end]) return false;
            start++; end--;
        }
        
        return true;
    }
    
    void backtrack(int start, vector<string> cur){
        if(start == str.size()) ans.push_back(cur);
        
        int end = start;
        while(end < str.size()){
            if(isPalindrome(start, end)){
                cur.push_back(str.substr(start, end-start+1));
                backtrack(end+1, cur);
                cur.pop_back();
            }
            end++;
        }
    }
    
    vector<vector<string>> partition(string s) {
        str = s;
        backtrack(0, {});
        
        return ans;
    }
};