題目描述：給定一個字串 s 和一個單字字典 wordDict，將 s 分割成一或多個字典中的單字，返回所有可能的分割結果（以空格分隔的句子）。
解題思路：使用記憶化 DFS（Top-Down）。定義遞迴函數 dfs(start)，回傳從索引 start 開始能分割 s[start:] 的所有句子列表。對每個起點，嘗試所有可能的前綴 s[start..end]，若該前綴在字典中，則遞迴求解 dfs(end + 1) 並拼接結果。邊界條件：start == n（已到達字串末尾），返回 {""}（空字串，代表一個完整路徑終點）。用 unordered_map<int, vector<string>> 快取每個起點的結果，避免重複計算。字典存入 unordered_set 以 O(1) 查詢，結合字元長度限制（最長單字長度）可剪枝。
時間複雜度：O(n^2 * 2^n) 最壞情況 — 若字典包含所有可能的子字串（如 s = "aaa...a"，dict = {"a", "aa", ...}），結果數量本身可達 2^n 級別，輸出主導複雜度。記憶化確保每個位置的子問題只計算一次，計算本身為 O(n^2)，但組合與複製字串的代價與輸出總長度成正比。
空間複雜度：O(n * 2^n) — 記憶化快取儲存所有位置的結果字串，最壞情況下總儲存量與所有可能句子的總字元數成正比。遞迴深度最多 O(n)，堆疊空間 O(n)。
1. Insert all words from wordDict into a hash set; compute maxLen
2. Define dfs(start):
a. If start in memo: return memo[start]
b. If start == n: return [""] (base case)
c. result = []
d. For end from start+1 to min(n, start+maxLen):
- word = s[start..end-1]
- If word in dict:
tails = dfs(end)
For each tail in tails:
if tail is empty: append word to result
else: append (word + " " + tail) to result
e. memo[start] = result; return result
3. Return dfs(0)方法一：純回溯（無記憶化） — O(n * 2^n) 不快取中間結果，直接從每個位置嘗試所有前綴並遞迴。當字串有大量重疊子問題時（如全為相同字符），同一個起點會被計算指數次，效率極低。
方法二：DP + 回溯重建路徑 — O(n^2 + 輸出)
先用動態規劃 dp[i] 記錄 s[0..i-1] 是否可被分割，同時記錄每個位置可由哪些前驅位置到達；再從 n 回溯重建所有有效路徑。優點是 DP 階段明確排除不可分割的字串（Early reject），避免在無解情況下遞迴；缺點是需要額外的前驅紀錄結構。適合先確認是否有解再列舉路徑的情境。