LC 131分割回文串Palindrome Partitioning　中等

把字符串 s 分割成若干子串，使每一段都是回文串，返回所有可行的分割方案。

思路 回溯：从 i 枚举分割点 j，s[i:j+1] 是回文则入 path 递归 j+1，到达末尾收集；O(n·2^n)。

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

        def dfs(i):
            if i == n:
                ans.append(path[:])
                return
            for j in range(i, n):
                t = s[i:j + 1]
                if t == t[::-1]:
                    path.append(t)
                    dfs(j + 1)
                    path.pop()

        dfs(0)
        return ans