题目：

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"]
  ]

思路：我们需要将一个字符串分割成回文子串的形式，然后返回所有的分割结果。需要两个辅助函数，一个是递归的DFS，帮助我们分割字符串，可以借鉴Restore IP Addresses的分割思想，我们循环所有的分割长度，从1开始直到剩余子串的长度（注意可以取等号i = s.size()），然后判断这个子串是否是回文，可以借鉴Valid Palindrome 中的方法，我们设置两个坐标从头尾判断，同时移动，如果有不相等返回false. 如果这个子串是回文，添加到tmp结果中，将剩余的字符串传给helper函数继续递归，直到剩余子串为空时，返回结果。重要的是，我们需要维护现场，将添加进去的子串结果pop_back出来。这样保证下次选择不同长度时，没有重复字符在结果中。

Attention:

1. 迭代终止条件，剩余子串长度为0.

if(s.size() == 0)
        {
            ret.push_back(tmp);
            return;
        }

int strlen = s.size();
                tmp.push_back(substr);
                partition_helper(s.substr(i, strlen - i), tmp, ret);
                tmp.pop_back();

for(int i = 1; i <= s.size(); i++)

复杂度：取决于结果的数量，最坏情况是指数量级的。

AC Code:

class Solution {
public:
    vector
  
   > partition(string s) {
        vector
   
    > ret; if(s.size() == 0) return ret; vector
    
      tmp; partition_helper(s, tmp, ret); return ret; } private: void partition_helper(string s, vector
     
       tmp, vector
      
       >& ret) { if(s.size() == 0) { ret.push_back(tmp); return; } for(int i = 1; i <= s.size(); i++) { string substr = s.substr(0, i); if(isPalindrome(substr)) { int strlen = s.size(); tmp.push_back(substr); partition_helper(s.substr(i, strlen - i), tmp, ret); tmp.pop_back(); } } } //假设不含空格等其他字符，只含小写字母 bool isPalindrome(string s) { int len = s.size(); if(len == 0 || len == 1) return true; int i = 0; int j = len - 1; while(i < j) { if(s[i++] != s[j--]) { return false; } } return true; } };