LeetCode 回文分割：遞歸回溯生成所有分割方案

題目描述

給定一個字符串 s，將其分割成若干子串，使每個子串都是回文串。要求列出所有可能的分割方案。

示例：

• 輸入："aab"
• 輸出：[["a","a","b"], ["aa","b"]]

解題思路：遞歸 + 回溯

採用最直觀的遞歸策略：將字符串分為「前綴」和「剩餘部分」。若前綴是回文，則對剩餘部分遞歸分割；否則嘗試更長的前綴。遞歸終止條件為字符串為空，此時將當前路徑加入結果集。

具體步驟：

1. 遍歷所有可能的分割點 i（從 0 到 len-1）
2. 檢查 s[0..i] 是否為回文
3. 若是，遞歸處理 s[i+1..end]，並將結果合併
4. 若否，繼續嘗試下一個分割點

Python 參考實現

class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        if not s:
            return [[]]
        
        result = []
        for i in range(len(s)):
            prefix = s[:i + 1]
            if self.isPalindrome(prefix):
                # 遞歸處理剩餘部分
                for rest in self.partition(s[i + 1:]):
                    result.append([prefix] + rest)
        return result
    
    def isPalindrome(self, s):
        return s == s[::-1]

if __name__ == "__main__":
    assert Solution().partition("aab") == [["a", "a", "b"], ["aa", "b"]]

複雜度分析

• 時間複雜度：最壞情況 O(N * 2^N)，其中 N 為字符串長度。每個位置可選分割或不分割，共 2^(N-1) 種分割方式，每種需 O(N) 驗證回文。
• 空間複雜度：O(N) 遞歸棧深度 + O(N * 2^N) 存儲結果。

優化方向

可引入 動態規劃預處理回文判斷（dp[i][j] 表示 s[i..j] 是否回文），將回文檢查從 O(N) 降為 O(1)；或使用 記憶化遞歸 避免重複計算子問題。對於長字符串，這些優化能顯著提升性能。