题意概括

给定一个字符串 s，要求将其分割成若干个子串，使得每个子串都是一个回文串。你需要返回所有可能的分割方案。

输入格式:

• 第一行为测试用例数量 T。
• 接下来 T 行，每行一个字符串 s。

输出格式:

• 对于每个测试用例，输出所有分割方案。
• 格式为 [ [方案1], [方案2], ... ]。每个方案中，子串用空格隔开。不同方案用逗号和空格隔开。

数据范围:

• $1 \le s.length \le 16$
• s 仅由小写英文字母组成。

基础知识

这是一个典型的搜索问题，可以通过 深度优先搜索 (DFS) + 回溯法 (Backtracking) 来解决。我们的目标是找到所有合法的切割点组合。

回溯算法的基本思路是：

1. 定义递归函数：我们设计一个递归函数，比如 dfs(start)，它的任务是寻找并分割字符串 s 从 start 索引开始的后缀部分。
2. 遍历选择：在 dfs(start) 中，我们从 start 位置开始，向后遍历，尝试将 s[start...i] 作为当前分割出的第一个子串。
3. 可行性剪枝：对于每一个尝试的子串 s[start...i]，我们首先要判断它是否是回文串。如果不是，就说明这个切割点 i 是不可行的，我们继续尝试下一个 i。
4. 深入递归：如果 s[start...i] 是一个回文串，我们就记录下这个子串，然后对剩下的部分 s[i+1...] 进行递归调用，即 dfs(i + 1)。
5. 回溯：当从 dfs(i + 1) 返回后，我们需要撤销刚才的选择（即从当前路径中移除子串 s[start...i]），以便尝试其他的切割可能性（例如，将 s[start...i+1] 作为一个整体）。
6. 终止条件：当 start 索引越过字符串末尾时，说明我们已经成功地将整个字符串分割完毕，此时就找到了一个完整的解决方案，将其保存下来。

优化： 为了避免在搜索过程中反复检查子串是否为回文，我们可以预先处理。使用动态规划，用一个二维数组 dp[i][j] 存储子串 s[i...j] 是否为回文串。这样，在DFS中判断回文的操作就从 $O(N)$ 降为了 $O(1)$。dp 表的预处理时间复杂度为 $O(N^2)$。

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

string s;
vector<vector<string>> ans;
vector<string> pth;
vector<vector<bool>> dp;
int n;

// isP 函数不再需要，被dp表替代

void dfs(int start) {
    // 如果起始位置已经超出字符串范围，说明找到了一组分割方案
    if (start >= n) {
        ans.push_back(pth);
        return;
    }

    for (int i = start; i < n; ++i) {
        // 检查 s[start...i] 是否是回文串
        if (dp[start][i]) {
            // 做出选择
            pth.push_back(s.substr(start, i - start + 1));
            // 进入下一层决策
            dfs(i + 1);
            // 撤销选择 (回溯)
            pth.pop_back();
        }
    }
}

void run() {
    cin >> s;
    n = s.length();
    
    // 清理上一组测试用例的结果
    ans.clear();
    pth.clear();

    // 预处理DP表，判断所有子串是否为回文
    dp.assign(n, vector<bool>(n, false));
    for (int i = n - 1; i >= 0; --i) {
        for (int j = i; j < n; ++j) {
            if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
            }
        }
    }

    dfs(0);

    // 按要求格式输出
    cout << "[ ";
    for (int i = 0; i < ans.size(); ++i) {
        if (i > 0) {
            cout << ", ";
        }
        cout << "[";
        for (int j = 0; j < ans[i].size(); ++j) {
            cout << ans[i][j] << (j == ans[i].size() - 1 ? "" : " ");
        }
        cout << "]";
    }
    cout << " ]\n";
}

int main() {
    // 关闭同步流
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--) {
        run();
    }

    return 0;
}

/*
样例 1:
输入:
2
aab
a
输出:
[ [a a b], [aa b] ]
[ [a] ]

样例 2:
输入:
1
abba
输出:
[ [a b b a], [a bb a], [abba] ]
*/