LeetCode Palindrome Partitioning：回溯法生成所有回文分割

題目大意

給定字符串 s，將其分割成若干子串，使每個子串都是回文。返回所有可能的分割方案。
例：s = "aab" → [["aa","b"], ["a","a","b"]]

回溯法核心思路

1. 遞歸函數：dfs(start, path)，start 為當前待分割起始索引，path 為已選子串列表
2. 終止條件：start == s.length()，將 path 加入結果集
3. 枚舉分割點：for end = start+1 .. s.length()
   • 子串 sub = s.substring(start, end)
   • 若 sub 是回文：path.add(sub)，遞歸 dfs(end, path)，回溯 path.removeLast()

回文判斷優化

預處理 isPal[i][j] 表示 s[i..j] 是否回文，O(N²) 預處理，O(1) 查詢。
DP 遞推：isPal[i][j] = (s[i]==s[j]) && (j-i<2 || isPal[i+1][j-1])

Java 完整實現

class Solution {
    List> res = new ArrayList<>();
    boolean[][] isPal;

    public List> partition(String s) {
        int n = s.length();
        isPal = new boolean[n][n];
        for (int i = n-1; i >= 0; --i)
            for (int j = i; j < n; ++j)
                isPal[i][j] = (s.charAt(i) == s.charAt(j)) && (j-i < 2 || isPal[i+1][j-1]);

        backtrack(s, 0, new ArrayList<>());
        return res;
    }

    void backtrack(String s, int start, List path) {
        if (start == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int end = start+1; end <= s.length(); ++end) {
            if (isPal[start][end-1]) {
                path.add(s.substring(start, end));
                backtrack(s, end, path);
                path.remove(path.size()-1);
            }
        }
    }
}

C++ 完整實現

class Solution {
public:
    vector> partition(string s) {
        int n = s.size();
        vector> isPal(n, vector(n));
        for (int i = n-1; i >= 0; --i)
            for (int j = i; j < n; ++j)
                isPal[i][j] = (s[i]==s[j]) && (j-i<2 || isPal[i+1][j-1]);

        vector> res;
        vector path;
        function dfs = [&](int start) {
            if (start == n) { res.push_back(path); return; }
            for (int end = start+1; end <= n; ++end) {
                if (isPal[start][end-1]) {
                    path.push_back(s.substr(start, end-start));
                    dfs(end);
                    path.pop_back();
                }
            }
        };
        dfs(0);
        return res;
    }
};

複雜度分析

• 預處理回文表：O(N²) 時間、O(N²) 空間
• 回溯搜索：最壞情況（全字符相同）分割數為 2^(N-1)，每個方案複製 O(N) → O(N × 2^N)
• 總體：指數級，但 N ≤ 16（LeetCode 限制）完全可行

優化變體：不預處理，在線判斷

若 N 很大或內存受限，可在回溯中雙指針判斷回文 O(len)，總複雜度仍為指數級但常數較小。

總結

經典回溯模板題。關鍵點：預處理回文表加速判斷、遞歸枚舉分割點、路徑回溯。代碼結構清晰，Java/C++ 實現均簡潔。掌握此模板可解決所有「字符串分割 + 子串性質約束」問題。