Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void helper(vector<vector<string>>& ans, vector<vector<int>>& pally, vector<string>& temp, string s, int index){
    if(index >= s.size()){
        ans.push_back(temp);
        return;
    }

    for(int len = 1; len + index <= s.size(); ++len){
        if(pally[index][index + len - 1]){
            temp.push_back(s.substr(index, len));
            helper(ans, pally, temp, s, index + len);
            temp.pop_back();
        }
    }
}

vector<vector<string>> partition(string s) {
    vector<vector<int>> pally(s.size(), vector<int>(s.size()));
    for(int i = 0; i < s.size(); ++i){
        for(int j = 0; j < s.size(); ++j)
            pally[i][j] = 0;
    }

    for(int i = 0; i < s.size(); ++i)
        pally[i][i] = 1;

    for(int i = 0; i < s.size() - 1; ++i){
        pally[i][i + 1] = (s[i] == s[i + 1]);
    }

    for(int gap = 2; gap < s.size(); ++gap){
        for(int i = gap; i <s.size(); ++i){
            int j = i - gap;
            pally[j][i] = (pally[j + 1][i - 1] && s[i] == s[j]);
        }
    }

    vector<vector<string>> ans;
    vector<string> temp;
    helper(ans, pally, temp, s, 0);
    return ans;
}