单词拆分 II 如何用回溯返回所有句子？为什么必须记忆化？

简化版

单词拆分 II 是从字符串当前位置开始枚举词典中可匹配的单词，递归拆分后缀，把所有后缀句子拼接回来。因为同一个后缀会被不同前缀反复访问，必须用 memo[index] 缓存从 index 开始能组成的所有句子。

详细版

状态可以定义为 dfs(index)：返回 s[index:] 能拆出的所有句子。若 index == s.length()，返回包含空串的列表，表示后缀已经拆完；否则枚举 end，当 s[index:end] 在词典中时，递归求 dfs(end)，再把当前单词和每个后缀句子拼接。

这题和普通单词拆分 I 的区别是：I 只判断是否存在，II 要返回所有方案，不能只用布尔 DP。记忆化仍然重要，因为后缀如 "sanddog" 可能从多个路径进入；缓存可以避免重复展开，但无法减少最终必须输出的句子数量。

复杂度与输出规模强相关，最坏可能指数级；记忆化主要减少重复子问题。

完整版教学

一、这题不是判断能不能拆，而是枚举所有拆法

输入：

s = "catsanddog"
wordDict = ["cat","cats","and","sand","dog"]

输出：

cats and dog
cat sand dog

普通单词拆分只要回答 true/false；单词拆分 II 必须把所有句子列出来，所以回溯返回的不是布尔值，而是“句子列表”。

二、状态定义：dfs(index) 返回后缀所有句子

最清晰的定义是：

dfs(index) = s[index:] 可以拆出的所有句子

例如 dfs(7) 对应后缀 "dog"，返回 ["dog"]；dfs(3) 对应后缀 "sanddog"，可以返回 ["sand dog"]。

记忆钩子：单词拆分 II 的递归函数不要只问“能不能”，要问“从这里开始能造出哪些句子”。

三、递归出口为什么返回包含空串的列表

当 index == s.length()，说明已经成功拆完整个字符串。为了让上一层能统一拼接，可以返回 [""]，表示“后面没有词了，但这条路径是成功的”。

当前词 = "dog"
后缀结果 = [""]
拼接后 = "dog"

如果返回空列表，上一层会以为没有可行后缀，反而丢掉合法句子。

四、为什么必须记忆化

同一个后缀可能被多个前缀路径访问。以 "pineapplepenapple" 为例，"apple" 这个后缀可能从 "pine apple pen" 和 "pineapple pen" 两条路径进入。

dfs(0)
├─ "pine" + dfs(4)
│  └─ "apple" + dfs(9)
└─ "pineapple" + dfs(9)

如果不缓存 dfs(9)，它会被重复计算。memo[index] 可以把“从 index 开始的所有句子”保存下来，下次直接复用。

五、代码模板

List<String> wordBreak(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    Map<Integer, List<String>> memo = new HashMap<>();
    return dfs(s, 0, dict, memo);
}

List<String> dfs(String s, int index, Set<String> dict, Map<Integer, List<String>> memo) {
    if (memo.containsKey(index)) return memo.get(index);
    if (index == s.length()) return Arrays.asList("");

    List<String> ans = new ArrayList<>();
    for (int end = index + 1; end <= s.length(); end++) {
        String word = s.substring(index, end);
        if (!dict.contains(word)) continue;
        for (String suffix : dfs(s, end, dict, memo)) {
            ans.add(suffix.isEmpty() ? word : word + " " + suffix);
        }
    }
    memo.put(index, ans);
    return ans;
}

如果词典中最长单词长度是 maxLen，循环的 end 可以限制到 index + maxLen，减少无意义 substring。

六、和 DP 的关系

这份写法是自顶向下记忆化搜索，本质上也是动态规划。它和布尔 DP 的区别在返回值：

题目	状态含义	返回值
单词拆分 I	`s[0:i]` 能否拆分	boolean
单词拆分 II	`s[index:]` 的所有拆法	`List<String>`

如果要进一步剪枝，可以先用布尔 DP 判断每个后缀是否可拆，回溯时遇到不可拆后缀直接跳过。

七、复杂度要和输出规模一起讲

因为题目要求返回所有句子，答案本身可能很多。比如字符串由很多个 a 组成，词典包含 "a", "aa", "aaa"，拆分方式会快速增长。

s = "aaaa"
dict = ["a","aa"]
拆法数量：5

因此不能承诺多项式时间。更准确的表达是：记忆化避免重复计算同一后缀，但总时间和空间至少与输出总字符数成正比。

八、常见误区与追问

误区：用布尔 DP 就能直接得到所有句子。 布尔 DP 只能判断可行性，枚举句子还要记录路径或后缀结果。
误区：递归出口返回空列表。 成功拆完时应返回包含空串的列表，方便上一层拼接。
误区：不做 memo 也能过。 多条路径会重复计算同一后缀，长字符串下会严重超时。
追问：memo 缓存什么？ 缓存从某个 index 开始能组成的所有句子列表。
追问：如何剪掉不可能后缀？ 可以先做单词拆分 I 的布尔 DP，回溯前检查后缀可行性。
追问：为什么复杂度仍可能指数级？ 因为输出句子数量本身可能指数级，算法必须把它们全部生成出来。

九、加强记忆

单词拆分 II 要记成“后缀返回句子列表”的题：dfs(index) 不只是判断后缀能否拆，而是返回所有后缀句子。递归出口返回 [""] 代表成功拆完，上一层按“当前词 + 后缀句子”拼接；memo[index] 缓存同一后缀的所有结果，避免重复搜索。面试中把它和单词拆分 I 对比讲清楚，再补一句输出规模可能指数级，就能覆盖主要追问。

简化版

详细版