Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = “aab”,
Return[
[“aa”,”b”],
[“a”,”a”,”b”]
]
最開始看到這道題時毫無思路，可能是看到回文就怕了。也想不出如何用回溯來求解。
於是在紙上隨便亂畫了一些，結果發現好像可以按照這個思路求解了，簡直囧啊。
對於上面的”aab”作為輸入，可以這麼尋找回文：
“a”+”ab”構成的回文串
“aa”+”b”構成的回文串
“aab”不是回文，所以直接退出。
於是感覺對於一個字符串，可以對這個字符串進行遍歷，如果前pos個字符串本身是個回文字符，那麼只需要求解後面的子字符的回文串即可，於是這個問題被分解成了一個更小的問題。這道題更像一個分治法的題，將問題規模不斷縮小，當然的遍歷字符串的過程中需要進行回溯。
除了需要一個進行遞歸的輔助函數外，還需要定義一個判斷一個字符串是否是回文字符串的輔助函數，程序的邏輯非常簡單。
這道題和Combination Sum 比較類似，一開始看到這道題時完全感覺無從下手，但是在紙上寫幾個測試用例，從特殊的測試用例中就可以發現規律了。加上回溯後的遞歸都沒有那麼一目了然，可能有測試用例會更容易懂一些。
runtime:20ms
class Solution {
public:
vector> partition(string s) {
vector path;
vector> result;
helper(s,0,path,result);
return result;
}
void helper(string s,int pos,vector & path,vector> & result)
{
if(pos==s.size())
{
result.push_back(path);
return ;
}
for(int i=pos;i
