131 Palindrome Partitioning

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

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<string> partition;
        vector<vector<string>> res;
        help(s,0,partition,res);
        return res;
    }
    void help(string s, int start_pos,vector<string> &partition, vector<vector<string>> &res)
    {
        if (start_pos>=s.size())
        {
            res.push_back(partition);
            return;
        }
        for (int end_pos = start_pos;end_pos<s.size();end_pos++)
        {
            if (isPalindrome(s,start_pos,end_pos))
            {
                partition.push_back(s.substr(start_pos,end_pos-start_pos+1));
                help(s,end_pos+1,partition,res);
                partition.pop_back();
            }
        }
    }
    bool isPalindrome(string s, int start_pos, int end_pos)
    {
        if (start_pos>=end_pos)
            return true;
        if (s[start_pos]!=s[end_pos])
            return false;
        return isPalindrome(s,start_pos+1,end_pos-1);
    }
};