字符串分割成回文串的所有方案 - 回溯算法详解

思路： 回溯法。从头开始遍历字符串，将每个位置作为回文串的起点，向后搜索所有的回文串，如果搜索到一个回文串，就将其加入当前的回文串列表中，并继续搜索后面的字符。如果搜索到最后一个字符，说明当前的回文串列表可以分割成为一个回文串分割方案，将其加入结果列表中。如果搜索的位置超出字符串长度，直接返回。

代码：

def partition(s: str) -> list[list[str]]:
    result = []
    def backtrack(index: int, path: list[str]):
        if index == len(s):
            result.append(path.copy())
            return
        for i in range(index, len(s)):
            if is_palindrome(s[index:i + 1]):
                path.append(s[index:i + 1])
                backtrack(i + 1, path)
                path.pop()
    def is_palindrome(substring: str) -> bool:
        return substring == substring[::-1]
    backtrack(0, [])
    return result