题目链接 · 灵神原题解（署名来源）

视频讲解

请看【基础算法精讲 14】，制作不易，欢迎点赞关注~

视频介绍了两种基本回溯思想：选或不选、枚举选哪个。

方法一：输入的视角（逗号选或不选）

假设每对相邻字符之间有个逗号，那么就看每个逗号是选还是不选。

也可以理解成：是否要在 $i$ 和 $i+1$ 处分割，把 $s[i]$ 作为当前子串的最后一个字符，把 $s[i+1]$ 作为下一个子串的第一个字符。

注意 $s[n-1]$ 一定是最后一个字符，所以在 $i=n-1$ 的时候一定要分割。

答疑

问：代码遇到回文串就加入 $\mathit{\text{path}}$，如何保证这种分割方案一定合法？

答：如果最后一个字符串不是回文串，我们不会递归到 $i=n$ 的边界，不会把不合法的分割加入答案。

Python 解法1

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        ans = []
        path = []

        # 现在 s 未被分割的部分为 [start, n-1]
        # 当前位于下标 i，讨论是否在 i 和 i+1 之间切一刀
        def dfs(i: int, start: int) -> None:
            if i == n:  # s 分割完毕
                ans.append(path.copy())  # 复制 path
                return

            # 不分割
            if i < n - 1:  # i=n-1 时必须分割（这是最后一段），i<n-1 时才可以不分割
                dfs(i + 1, start)

            # 分割，那么得到子串 [start, i]
            t = s[start: i + 1]
            if t == t[::-1]:  # 判断 t 是不是回文串
                path.append(t)
                # 现在 s 未被分割的部分为 [i+1, n-1]
                dfs(i + 1, i + 1)
                path.pop()  # 恢复现场

        dfs(0, 0)
        return ans

C++ 解法1

// C++ 版待补充

C++ 解法2

class Solution {
    bool is_palindrome(const string& s, int left, int right) {
        while (left < right) {
            if (s[left++] != s[right--]) {
                return false;
            }
        }
        return true;
    }

public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        vector<vector<string>> ans;
        vector<string> path;

        // 现在 s 未被分割的部分为 [start, n-1]
        // 当前位于下标 i，讨论是否在 i 和 i+1 之间切一刀
        auto dfs = [&](this auto&& dfs, int i, int start) {
            if (i == n) { // s 分割完毕
                ans.emplace_back(path);
                return;
            }

            // 不分割
            if (i < n - 1) { // i=n-1 时必须分割（这是最后一段），i<n-1 时才可以不分割
                dfs(i + 1, start);
            }

            // 分割，那么得到子串 [start, i]
            if (is_palindrome(s, start, i)) { // 判断子串 [start, i] 是不是回文串
                path.emplace_back(s.substr(start, i - start + 1));
                // 现在 s 未被分割的部分为 [i+1, n-1]
                dfs(i + 1, i + 1);
                path.pop_back(); // 恢复现场
            }
        };

        dfs(0, 0);
        return ans;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n{2}^n)$，其中 $n$ 为 $s$ 的长度。每次都是选或不选，递归次数为一个满二叉树的节点个数，那么一共会递归 $\mathcal{O}(2^n)$ 次（等比数列和），再算上判断回文和加入答案时需要 $\mathcal{O}(n)$ 的时间，所以时间复杂度为 $\mathcal{O}(n{2}^n)$。
• 空间复杂度：$\mathcal{O}(n)$。返回值的空间不计。

方法二：答案的视角（枚举子串结束位置）

Python 解法3

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        ans = []
        path = []

        # 现在 s 未被分割的部分为 [i, n-1]
        # 枚举下一刀切在哪
        def dfs(i: int) -> None:
            if i == n:  # s 分割完毕
                ans.append(path.copy())  # 复制 path
                return
            for j in range(i, n):  # 枚举子串的结束位置
                t = s[i: j + 1]  # 分割出子串 t
                if t == t[::-1]:  # 判断 t 是不是回文串
                    path.append(t)
                    # 考虑剩余的 s[j+1:] 怎么分割
                    dfs(j + 1)
                    path.pop()  # 恢复现场

        dfs(0)
        return ans

C++ 解法3

// C++ 版待补充

C++ 解法4

class Solution {
    bool isPalindrome(const string& s, int left, int right) {
        while (left < right) {
            if (s[left++] != s[right--]) {
                return false;
            }
        }
        return true;
    }

public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        vector<vector<string>> ans;
        vector<string> path;

        // 现在 s 未被分割的部分为 [i, n-1]
        // 枚举下一刀切在哪
        auto dfs = [&](this auto&& dfs, int i) {
            if (i == n) { // s 分割完毕
                ans.emplace_back(path);
                return;
            }
            for (int j = i; j < n; j++) { // 枚举子串的结束位置
                if (isPalindrome(s, i, j)) { // 判断 [i, j] 是不是回文串
                    path.push_back(s.substr(i, j - i + 1)); // 分割！
                    // 现在 s 未被分割的部分为 [j+1, n-1]
                    dfs(j + 1);
                    path.pop_back(); // 恢复现场
                }
            }
        };

        dfs(0);
        return ans;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n{2}^n)$，其中 $n$ 为 $s$ 的长度。答案的长度至多为逗号子集的个数，即 $\mathcal{O}(2^n)$，因此会递归 $\mathcal{O}(2^n)$ 次，再算上判断回文和加入答案时需要 $\mathcal{O}(n)$ 的时间，所以时间复杂度为 $\mathcal{O}(n{2}^n)$。
• 空间复杂度：$\mathcal{O}(n)$。返回值的空间不计入。

专题训练

见下面回溯题单的「§4.3 划分型回溯」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府