本文详解如何修正递归函数，使其能正确统计用词表中单词（可重复使用）拼出目标字符串的所有方案数，并给出可运行、带调试输出的优化实现。
本文详解如何修正递归函数，使其能正确统计用词表中单词（可重复使用）拼出目标字符串的所有方案数，并给出可运行、带调试输出的优化实现。
在原始代码中，count_construct 函数试图通过索引控制词表遍历顺序，但其核心逻辑存在根本性限制：它采用“每个单词至多选一次”的回溯策略（类似子集和问题），即 index 递增后不再回退，导致无法多次选用同一单词（如 "p" 在 "p+ur+p+le" 中需被使用两次）。这与题目要求的「单词可无限复用」相悖。
要支持重复使用，关键在于放弃固定索引推进，改为对整个词表进行无状态遍历——每次递归调用都重新检查所有单词是否可接在当前字符串之后。同时，为避免字符串拼接开销过大，推荐使用字符长度匹配而非完整拼接判断。
以下是修正后的专业级递归实现（含记忆化优化，兼顾清晰性与效率）：
def count_construct(target, word_bank):
# 使用缓存避免重复计算相同剩余目标的子问题
memo = {}
def helper(remaining):
# 基础情况：已完全匹配
if remaining == "":
return 1
# 缓存命中
if remaining in memo:
return memo[remaining]
total = 0
# 尝试每个单词：若能作为 remaining 的前缀，则递归处理剩余部分
for word in word_bank:
if remaining.startswith(word):
new_remaining = remaining[len(word):]
total += helper(new_remaining)
memo[remaining] = total
return total
return helper(target)✅ 验证示例：
target_example = "purple" word_bank_example = ["purp", "p", "ur", "le", "purpl"] print(count_construct(target_example, word_bank_example)) # 输出：2
该实现正确返回 2，对应两种合法组合：
- "purp" + "le"
- "p" + "ur" + "p" + "le"
关键设计说明：
- helper(remaining) 接收剩余待匹配的字符串，而非已构建的前缀，逻辑更直观且天然支持重复；
- remaining.startswith(word) 高效判断单词是否可用，避免字符串拼接与长度比较冗余；
- memo 字典实现自顶向下记忆化，将时间复杂度从指数级优化至 O(n * m)（n 为 target 长度，m 为 word_bank 大小）；
- 无需维护全局状态或手动 pop，函数纯正、线程安全、易于测试。
⚠️ 注意事项：
- 若词表含空字符串 ""，将导致无限递归，调用前建议过滤：word_bank = [w for w in word_bank if w]；
- 对于超长 target 或极大 word_bank，需考虑栈深度限制，生产环境可改用迭代 DFS 或 BFS；
- 此解法统计的是方案数量；若需枚举所有方案，应改用生成器或累积路径列表（如答案中 current 列表方式），但会显著增加空间开销。
综上，解决「可重复使用单词」的递归问题，核心在于转变状态定义——从“已选哪些单词”转向“还剩什么要匹配”，并辅以合理剪枝与缓存，即可兼顾正确性、性能与代码可维护性。
