給定字串
s與字典wordDict，在s中加空格組成句子，使每個詞都在字典裡。回傳所有可能的句子（任意順序）。
Example:
Input: s = “catsanddog”, wordDict = [“cat”,“cats”,“and”,“sand”,“dog”] Output: [“cats and dog”, “cat sand dog”]
Input: s = “pineapplepenapple”, wordDict = [“apple”,“pen”,“applepen”,“pine”,“pineapple”] Output: [“pine apple pen apple”,“pineapple pen apple”,“pine applepen apple”]
Intuition
TIP
核心思路：回溯列舉所有切法，但用「起點索引 → 該後綴的所有句子」做記憶化，避免同一後綴被重複展開（指數退化）。
- 從
start嘗試每個字典詞當開頭，遞迴解剩餘後綴 - 把「從
start開始能組出的所有句子」快取在memo[start] - 139 Word Break 只問「能否」（布林 DP）；本題要列所有解，故回溯 + 記憶化
- 可選的剪枝：先用 139 的 DP 判斷
s是否可切，不行直接回空，避免最壞情況爆炸
Approaches
⭐ Backtracking + Memoization (cache suffix by start) — O(n² + total output) / O(n · #results)
- Idea: DFS 每個起點嘗試所有字典詞開頭，
memo[start]快取後綴的所有組合 - Time: 取決於解的數量；記憶化避免重算同一後綴
- Space:
O(n · 解數)- memo 與遞迴
class Solution {
fun wordBreak(s: String, wordDict: List<String>): List<String> {
val words = wordDict.toHashSet()
return backtrack(s, 0, words, HashMap())
}
private fun backtrack(
s: String, start: Int, words: Set<String>, memo: HashMap<Int, List<String>>,
): List<String> {
memo[start]?.let { return it }
val res = ArrayList<String>()
if (start == s.length) {
res.add("") // 到底：回傳一個空句子作為拼接基底
return res
}
for (end in start + 1..s.length) {
val word = s.substring(start, end)
if (word in words) {
for (sub in backtrack(s, end, words, memo)) {
res.add(if (sub.isEmpty()) word else "$word $sub")
}
}
}
memo[start] = res
return res
}
}Note: Prune with 139's DP first
像 s = "aaaa...ab"、字典只有 a 這種無解但組合爆炸的輸入，回溯會做大量白工。先用 139 Word Break 的布林 DP 判斷「s 是否可被切分」，不可切就直接回傳空清單，可有效避免最壞情況的指數展開。
🔑 Takeaways
- Pattern: 回溯列舉所有解 + 記憶化（以起點為 key 快取後綴解）
- Key trick: 到達字串尾端回傳含空字串的清單，作為上層拼接的基底；用
memo[start]避免重算同一後綴。與 139（只問可否、布林 DP）成對理解：「可否」用 DP、「列所有解」用回溯 + memo