给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: “aab”
输出:
[
[“aa”,“b”],
[“a”,“a”,“b”]
]

解析：遇到这种需要返回所有可能方案的题目，应该思考是否可以用回溯法解决。
本题采用回溯法加剪枝来解决。
见图
对于字符串aab,我们尝试在它的每一位进行截断，并对截下来的前半段进行判定，如果前半段是回文串，则将其记录，并将剩下的后半段递归调用函数，直到字符串为空。
而如果前半段不是回文串，则直接剪枝跳过。

在整个过程中，存在需要多次判定同一部分是否为回文串的可能
为了减少重复计算耗时，在回溯之前，使用动态规划的方法先行计算出每一段是否为回文串。

定义二维数组dp[s.size()][s.size()]
对于dp[i][j]表示字符串从第i个字符到第j个字符这一段是否为回文串
列出状态转移方程
dp[i][j] = (s[i]==s[j]) && (r-l<=2||dp[i+1][j-1])

下面是完整代码

class Solution {
public:vector<vector<string>> partition(string s) {vector<vector<char>> dp(s.size(),vector<char>(s.size(),0));for(int r=0;r<s.size();++r){for(int l=0;l<=r;++l){if(s[l]==s[r] && (r-l<=2||dp[l+1][r-1])) dp[l][r]=1;}}vector<vector<string>> res;vector<string> tmp;backtrace(dp,res,tmp,s,0);return res;}void backtrace(vector<vector<char>> &dp,vector<vector<string>> &res,vector<string> &tmp,string &s,int now){if(now>=s.size()) return res.push_back(tmp);for(int i=now;i<s.size();++i){if(!dp[now][i]) continue;tmp.push_back(s.substr(now,i-now+1));backtrace(dp,res,tmp,s,i+1);tmp.pop_back();}}
};