# 131-Palindrome Partitioning
###### tags: `Medium`
* Question:
https://leetcode.com/problems/palindrome-partitioning/

>Key:
1. 如何檢查回文?
2. 如何避免重複回文組合放入陣列?
3. Backtracking
每個子字串都是由字串選跟不選所組成，加上每次迭代都會檢查是否為回文，因此最後遞迴結果一定是回文

>Reference:
https://medium.com/@ChYuan/leetcode-131-palindrome-partitioning-%E5%BF%83%E5%BE%97-medium-1d5a8d6240f6

## Backtracking Solution

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> result;
        vector<string> path;
        partition(s, 0, path, result);//dfs calls
        return result;
    }
private: 
    //DFS steps
    void partition(string& s, int start, vector<string>& path, vector<vector<string>>& result) {
        int n = s.length();
        if (start == n) {
            result.push_back(path);
        } else {
            for (int i = start; i < n; i++) {
                if (isPalindrome(s, start, i)) {
                    path.push_back(s.substr(start, i - start + 1));
                    partition(s, i + 1, path, result);
                    path.pop_back();
                }
            }
        }
    }
    //helper function to safe check whether a substr is palindrome or not
    bool isPalindrome(string& s, int l, int r) {
        while (l < r) {
            if (s[l++] != s[r--]) {
                return false;
            }
        }
        return true;
    }
};

* Note:
1. string STL的substr用法
https://crmne0707.pixnet.net/blog/post/316362030-c%2B%2B-%E5%AD%90%E5%AD%97%E4%B8%B2-substring