本文详解如何修正递归函数，使其支持从词库中重复选取同一单词来拼凑目标字符串，并给出正确、高效、可读性强的实现方案。
本文详解如何修正递归函数，使其支持从词库中**重复选取同一单词**来拼凑目标字符串，并给出正确、高效、可读性强的实现方案。
在原始代码中，count_construct 函数采用索引 index 控制词库遍历顺序，每次递归调用要么“包含当前词”（helper(index, ...)），要么“跳过当前词”（helper(index + 1, ...)）。这种设计本质上模拟了子集枚举——每个单词最多被使用一次，因此无法生成如 "p" + "ur" + "p" + "le" 这类需重复使用 "p" 的合法组合，导致结果偏小（返回 1 而非正确的 2 或更多）。
要支持无限次复用任意单词，关键在于：递归分支不应受限于词库索引的单向推进，而应允许每次从整个 word_bank 中自由选择。同时，为避免无效穷举，我们采用前缀匹配剪枝：仅当 word 能匹配 target 当前剩余前缀时，才尝试选用该词。
以下是优化后的标准实现（无全局变量、无副作用、纯递归、清晰易懂）：
def count_construct(target, word_bank):
# 基础情况：已完全匹配
if target == "":
return 1
total = 0
# 尝试每个单词作为当前前缀
for word in word_bank:
# 检查是否能匹配 target 开头
if len(word) <= len(target) and target.startswith(word):
remainder = target[len(word):] # 剩余待匹配部分
total += count_construct(remainder, word_bank) # 递归求解剩余部分
return total
# 测试用例
target_example = "purple"
word_bank_example = ["purp", "p", "ur", "le", "purpl"]
print(count_construct(target_example, word_bank_example)) # 输出: 2✅ 为什么这个版本正确？
- 每次递归都对整个 word_bank 进行遍历，"p" 可在不同递归层级被多次选用；
- target.startswith(word) 确保只探索合法路径，避免无效拼接（如 "le" 放在 "purple" 开头）；
- remainder = target[len(word):] 精确推进匹配位置，天然支持重叠与复用；
- 无状态变量、无 nonlocal/global，函数纯净、可测试、易推理。
⚠️ 注意事项：
- 该算法时间复杂度为指数级（最坏 O(n^m)，其中 m 是 target 长度，n 是词库大小），对长目标或大词库可能较慢；
- 实际项目中建议添加记忆化（memoization） 缓存已计算的 target 子问题结果，将时间复杂度优化至 O(m × n × k)（k 为平均单词长度）；
- 若需枚举所有方案而非仅计数，可改用生成器或传入 path 列表收集路径（如答案中 print(f'Found solution: {current}') 所示）。
总结：递归设计的核心在于正确定义子问题。本例中，“构造 target” 的子问题是“构造 target[len(word):]”，而非“从第 i 个词开始构造”。抛弃索引依赖、拥抱语义化子问题划分，是解决此类可重复组合问题的关键。
