题目
给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例
示例 1：
输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]示例 2：
输入：s = "a" 输出：[["a"]]
分析
要将字符串 s 分割成一些子串，使得每个子串都是回文串，并返回所有可能的分割方案，可以使用回溯算法来解决这个问题。回溯算法通过递归的方式尝试所有可能的分割方案，同时利用动态规划来预先判断子串是否为回文串，以减少重复计算。
回溯+动态规划
代码解释
partition 函数：
首先初始化 isPalindrome 数组。使用动态规划计算所有子串是否为回文串。对于长度为 1 或 2 的子串，直接判断首尾字符是否相等；对于长度大于 2 的子串，需要同时满足首尾字符相等且中间子串也是回文串。
调用 backtrack 函数开始生成分割方案。返回所有可能的分割方案。
backtrack 函数：
该函数是回溯算法的核心，用于生成所有可能的分割方案。
如果 start 等于字符串的长度，说明已经遍历完字符串，将当前分割方案加入结果集。
遍历从 start 到字符串末尾的所有可能的子串，如果该子串是回文串，将其加入当前分割方案，然后递归调用 backtrack 函数处理剩余的字符串，最后回溯，撤销选择。
时间复杂度：O()，
是字符串的长度，最坏情况下字符串的每个位置都可以作为分割点，因此有
种分割方案，对于每种方案，需要 O(
) 的时间来判断子串是否为回文串。
空间复杂度：O()
class Solution {
private:
// 存储所有可能的分割方案
std::vector<std::vector<std::string>> result;
// 存储当前的分割方案
std::vector<std::string> current;
// 二维数组，用于存储子串是否为回文串的信息
std::vector<std::vector<bool>> isPalindrome;
// 回溯函数，用于生成所有可能的分割方案
void backtrack(const std::string& s, int start) {
if (start == s.length()) {
// 如果已经遍历完字符串，将当前分割方案加入结果集
result.push_back(current);
return;
}
for (int end = start; end < s.length(); ++end) {
if (isPalindrome[start][end]) {
// 如果当前子串是回文串，将其加入当前分割方案
current.push_back(s.substr(start, end - start + 1));
// 递归调用回溯函数，继续处理剩余的字符串
backtrack(s, end + 1);
// 回溯，撤销选择
current.pop_back();
}
}
}
public:
std::vector<std::vector<std::string>> partition(std::string s) {
int n = s.length();
// 初始化 isPalindrome 数组
isPalindrome.resize(n, std::vector<bool>(n, false));
// 动态规划计算所有子串是否为回文串
for (int len = 1; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
int j = i + len - 1;
if (s[i] == s[j]) {
if (len <= 2 || isPalindrome[i + 1][j - 1]) {
isPalindrome[i][j] = true;
}
}
}
}
// 调用回溯函数开始生成分割方案
backtrack(s, 0);
return result;
}
};