2 DP methods are used in this implementation:
1. DP method to find all palindromes in string s:
This one is talk thoroughly in before...
2. DP method to find all partitions in string s:
If sub-string
s[i..j] is a palindrome, then all partitions for s[0..j] is all partitions for s[0..i-1] + palindromes[i..j]
Code with explanations:
vector<vector<string> > partition(string s){ int n = s.size(); //pal[i][j]: substring s[i..j] is a palindrome or not vector<vector<bool> > pal(n, vector<bool>(n, false)); //solution[i + 1]: all partitions for substring s[0..i] vector<vector<vector<string> > > solution(n + 1); //solution[0] is a empty matrix: partition for substrings[0..-1] solution[0].push_back(vector<string>(0)); for(int j = 0; j < n; ++j) for(int i = 0; i <= j; ++i) if(s[i] == s[j] && (j - i < 2 || pal[i + 1][j - 1])){ pal[i][j] = true; //DP method: all partitions for s[0..j]: all partitions for s[0..i-1] + palindromes[i..j] for(int k = 0; k < solution[i].size(); ++k){ //solution[i]: all partitions for s[0..i-1] solution[i][k].push_back(s.substr(i, j - i + 1)); //add palindromes[i..j] solution[j + 1].push_back(solution[i][k]); //solution[j + 1]: all partitions for s[0..j] solution[i][k].pop_back(); //be sure to recover solution[i] for later use } } return solution[n]; }