动态规划和回溯算法的思维转换

labuladong约 13224 字大约 44 分钟动态规划设计

Info

数据结构精品课open in new window 和递归算法专题课open in new window 限时附赠网站会员，全新纸质书《labuladong 的算法笔记》open in new window 出版，签名版限时半价！

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
139. Word Breakopen in new window	139. 单词拆分open in new window	🟠
140. Word Break IIopen in new window	140. 单词拆分 IIopen in new window	🔴

之前手把手带你刷二叉树（纲领篇）把递归穷举划分为「遍历」和「分解问题」两种思路，其中「遍历」的思路扩展延伸一下就是回溯算法，「分解问题」的思路可以扩展成动态规划算法。

我在手把手带你刷二叉树（思路篇）对一些二叉树问题进行举例，同时给出「遍历」和「分解问题」两种思路的解法，帮大家借助二叉树理解更高级的算法设计思想。

当然，这种思维转换不止局限于二叉树相关的算法，本文就跳出二叉树类型问题，来看看实际算法题中如何把问题抽象成树形结构，从而进行「遍历」和「分解问题」的思维转换，从回溯算法顺滑地切换到动态规划算法。

先说句题外话，前文动态规划核心框架详解说，标准的动态规划问题一定是求最值的，因为动态规划类型问题有一个性质叫做「最优子结构」，即从子问题的最优解推导出原问题的最优解。

但在我们平常的语境中，就算不是求最值的题目，只要看见使用备忘录消除重叠子问题，我们一般都称它为动态规划算法。严格来讲这是不符合动态规划问题的定义的，说这种解法叫做「带备忘录的 DFS 算法」可能更准确些。不过咱也不用太纠结这种名词层面的细节，既然大家叫的顺口，就叫它动态规划也无妨。

本文讲解的两道题目也不是求最值的，但依然会把他们的解法称为动态规划解法，这里提前跟大家说下这里面的细节，免得细心的读者疑惑。其他不多说了，直接看题目吧。

单词拆分 I

首先看下力扣第 139 题「单词拆分open in new window」：

函数签名如下：

boolean wordBreak(String s, List<String> wordDict);

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

bool wordBreak(string s, vector<string>& wordDict);

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def wordBreak(s: str, wordDict: List[str]) -> bool:

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func wordBreak(s string, wordDict []string) bool {}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var wordBreak = function(s, wordDict) {
    // function body here
};

这是一道非常高频的面试题，我们来思考下如何通过「遍历」和「分解问题」的思路来解决它。

先说说「遍历」的思路，也就是用回溯算法解决本题。回溯算法最经典的应用就是排列组合相关的问题了，不难发现这道题换个说法也可以变成一个排列问题：

现在给你一个不包含重复单词的单词列表 wordDict 和一个字符串 s，请你判断是否可以从 wordDict 中选出若干单词的排列（可以重复挑选）构成字符串 s。

这就是前文回溯算法秒杀排列组合问题的九种变体中讲到的最后一种变体：元素无重可复选的排列问题，前文我写了一个 permuteRepeat 函数，代码如下：

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> track = new LinkedList<>();

    // 元素无重可复选的全排列
    public List<List<Integer>> permuteRepeat(int[] nums) {
        backtrack(nums);
        return res;
    }

    // 回溯算法核心函数
    void backtrack(int[] nums) {
        // base case，到达叶子节点
        if (track.size() == nums.length) {
            // 收集根到叶子节点路径上的值
            res.add(new LinkedList(track));
            return;
        }

        // 回溯算法标准框架
        for (int i = 0; i < nums.length; i++) {
            // 做选择
            track.add(nums[i]);
            // 进入下一层回溯树
            backtrack(nums);
            // 取消选择
            track.removeLast();
        }
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class Solution {
public:
    vector<vector<int>> res;
    deque<int> track;

    // 元素无重可复选的全排列
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end()); // 先对数组进行排序
        backtrack(nums, vector<bool>(nums.size(), false));
        return res;
    }

    // 回溯算法核心函数
    void backtrack(vector<int>& nums, vector<bool>& used) {
        // base case，到达叶子节点
        if (track.size() == nums.size()) {
            // 收集根到叶子节点路径上的值
            res.push_back(vector<int>(track.begin(), track.end()));
            return;
        }

        // 回溯算法标准框架
        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) continue; // 当前值已经被加入track，跳过
            if (i > 0 && nums[i - 1] == nums[i] && !used[i - 1]) continue; // 对于重复元素，跳过

            // 做选择
            track.push_back(nums[i]);
            used[i] = true;
            // 进入下一层回溯树
            backtrack(nums, used);
            // 取消选择
            track.pop_back();
            used[i] = false;
        }
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

from typing import List

class Solution:
    def __init__(self):
        # 保存结果的二维列表
        self.res = []
        # 保存回溯路径的链表
        self.track = []

    # 定义接收参数为整数列表，返回结果为整数列表的函数，函数名与 Java 代码相同
    # 原 Java 代码为泛型函数，Python 对应的类型实现方式为类型注解
    def permuteRepeat(self, nums: List[int]) -> List[List[int]]:
        # 调用 backtrack 函数，得到结果
        self.backtrack(nums)
        # 返回结果
        return self.res

    # 回溯算法的核心函数
    def backtrack(self, nums):
        # 回溯树中到达叶子节点，即收集一个排列
        if len(self.track) == len(nums):
            # 用排列的拷贝记录路径
            self.res.append(self.track.copy())
            return
        
        # 回溯算法标准框架
        for i in range(len(nums)):
            # 做选择
            self.track.append(nums[i])
            # 进入下一层回溯树
            self.backtrack(nums)
            # 取消选择
            self.track.pop()

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func permuteRepeat(nums []int) [][]int {
    res := [][]int{}
    track := []int{}

    // 回溯算法核心函数
    var backtrack func([]int)
    backtrack = func(nums []int) {
        n := len(nums)
        // base case，到达叶子节点
        if len(track) == n {
            // 收集根到叶子节点路径上的值
            temp := make([]int, n)
            copy(temp, track)
            res = append(res, temp)
            return
        }

        // 回溯算法标准框架
        for i := 0; i < n; i++ {
            // 做选择
            track = append(track, nums[i])
            // 进入下一层回溯树
            backtrack(nums)
            // 取消选择
            track = track[:len(track)-1]
        }
    }

    backtrack(nums)
    return res
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var permuteRepeat = function(nums) {
  const res = [];
  const track = [];
  backtrack(nums);
  return res;

  function backtrack(nums) {
    if (track.length === nums.length) { 
      res.push([...track]); // 将列表添加到result中
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      track.push(nums[i]); // 做选择
      backtrack(nums);    // 进入下一层回溯树
      track.pop();         // 取消选择
    }
  }
};

给这个函数输入 nums = [1,2,3]，输出是 3^3 = 27 种可能的组合：

[
  [1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3],
  [2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3],
  [3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]
]

这段代码实际上就是遍历一棵高度为 N + 1 的满 N 叉树（N 为 nums 的长度），其中根到叶子的每条路径上的元素就是一个排列结果：

类比一下，本文讲的这道题也有异曲同工之妙，假设 wordDict = ["a", "aa", "ab"], s = "aaab"，想用 wordDict 中的单词拼出 s，其实也面对着类似的一棵 M 叉树，M 为 wordDict 中单词的个数，你需要做的就是站在回溯树的每个节点上，看看哪个单词能够匹配 s[i..] 的前缀，从而判断应该往哪条树枝上走：

然后，按照前文回溯算法框架详解所说，你把 backtrack 函数理解成在回溯树上游走的一个指针，维护每个节点上的变量 i，即可遍历整棵回溯树，寻找出匹配 s 的组合。

回溯算法解法代码如下：

class Solution {
    List<String> wordDict;
    // 记录是否找到一个合法的答案
    boolean found = false;
    // 记录回溯算法的路径
    LinkedList<String> track = new LinkedList<>();

    // 主函数
    public boolean wordBreak(String s, List<String> wordDict) {
        this.wordDict = wordDict;
        // 执行回溯算法穷举所有可能的组合
        backtrack(s, 0);
        return found;
    }

    // 回溯算法框架
    void backtrack(String s, int i) {
        // base case
        if (found) {
            // 如果已经找到答案，就不要再递归搜索了
            return;
        }
        if (i == s.length()) {
            // 整个 s 都被匹配完成，找到一个合法答案
            found = true;
            return;
        }

        // 回溯算法框架
        for (String word : wordDict) {
            // 看看哪个单词能够匹配 s[i..] 的前缀
            int len = word.length();
            if (i + len <= s.length()
                && s.substring(i, i + len).equals(word)) {
                // 找到一个单词匹配 s[i..i+len)
                // 做选择
                track.addLast(word);
                // 进入回溯树的下一层，继续匹配 s[i+len..]
                backtrack(s, i + len);
                // 撤销选择
                track.removeLast();
            }
        }
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class Solution {
private:
    vector<string> wordDict;
    // 记录是否找到一个合法的答案
    bool found = false;
    // 记录回溯算法的路径
    deque<string> track;

public:
    // 主函数
    bool wordBreak(string s, vector<string>& wordDict) {
        this->wordDict = wordDict;
        // 执行回溯算法穷举所有可能的组合
        backtrack(s, 0);
        return found;
    }

    // 回溯算法框架
    void backtrack(string& s, int i) {
        // base case
        if (found) {
            // 如果已经找到答案，就不要再递归搜索了
            return;
        }
        if (i == s.size()) {
            // 整个 s 都被匹配完成，找到一个合法答案
            found = true;
            return;
        }

        // 回溯算法框架
        for (string& word : wordDict) {
            // 看看哪个单词能够匹配 s[i..] 的前缀
            int len = word.size();
            if (i + len <= s.size()
                && s.substr(i, len) == word) {
                // 找到一个单词匹配 s[i..i+len)
                // 做选择
                track.push_back(word);
                // 进入回溯树的下一层，继续匹配 s[i+len..]
                backtrack(s, i + len);
                // 撤销选择
                track.pop_back();
            }
        }
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

from typing import List

class Solution:
    def __init__(self):
        self.wordDict = []
        # 记录是否找到一个合法的答案
        self.found = False
        # 记录回溯算法的路径
        self.track = []

    # 主函数
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        self.wordDict = wordDict
        # 执行回溯算法穷举所有可能的组合
        self.backtrack(s, 0)
        return self.found

    # 回溯算法框架
    def backtrack(self, s: str, i: int):
        # base case
        if self.found:
            # 如果已经找到答案，就不要再递归搜索了
            return
        if i == len(s):
            # 整个 s 都被匹配完成，找到一个合法答案
            self.found = True
            return

        # 回溯算法框架
        for word in self.wordDict:
            # 看看哪个单词能够匹配 s[i..] 的前缀
            length = len(word)
            if i + length <= len(s) and s[i:i+length] == word:
                # 找到一个单词匹配 s[i..i+length)
                # 做选择
                self.track.append(word)
                # 进入回溯树的下一层，继续匹配 s[i+length..]
                self.backtrack(s, i+length)
                # 撤销选择
                self.track.pop()

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func wordBreak(s string, wordDict []string) bool {
    // 记录是否找到一个合法的答案
    found := false
    // 记录回溯算法的路径
    track := []string{}

    // 回溯算法框架
    var backtrack func(i int)
    backtrack = func(i int) {
        // base case
        if found {
            // 如果已经找到答案，就不要再递归搜索了
            return
        }
        if i == len(s) {
            // 整个 s 都被匹配完成，找到一个合法答案
            found = true
            return
        }

        // 回溯算法框架
        for _, word := range wordDict {
            // 看看哪个单词能够匹配 s[i..] 的前缀
            length := len(word)
            if i+length <= len(s) && s[i:i+length] == word {
                // 找到一个单词匹配 s[i..i+len)
                // 做选择
                track = append(track, word)
                // 进入回溯树的下一层，继续匹配 s[i+len..]
                backtrack(i+length)
                // 撤销选择
                track = track[:len(track)-1]
            }
        }
    }

    // 执行回溯算法穷举所有可能的组合
    backtrack(0)
    return found
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
    let found = false;
    let track = [];

    /**
     * @param {string} s
     * @param {number} i
     * @return {void}
     */
    function backtrack(s, i) {
        // base case
        if (found) {
            // 如果已经找到答案，就不要再递归搜索了
            return;
        }
        if (i == s.length) {
            // 整个 s 都被匹配完成，找到一个合法答案
            found = true;
            return;
        }
        // 回溯算法框架
        for (let word of wordDict) {
            // 看看哪个单词能够匹配 s[i..] 的前缀
            let len = word.length;
            if (i + len <= s.length && s.substring(i, i + len) == word) {
                // 找到一个单词匹配 s[i..i+len)
                // 做选择
                track.push(word);
                // 进入回溯树的下一层，继续匹配 s[i+len..]
                backtrack(s, i + len);
                // 撤销选择
                track.pop();
            }
        }
    }
    
    backtrack(s, 0);
    return found;
};

这段代码就是严格按照回溯算法框架写出来的，应该不难理解，但这段代码无法通过所有测试用例，我们按照之前算法时空复杂度使用指南中讲到的方法来分析一下它的时间复杂度。

递归函数的时间复杂度的粗略估算方法就是用递归函数调用次数（递归树的节点数） x 递归函数本身的复杂度。对于这道题来说，递归树的每个节点其实就是对 s 进行的一次切割，那么最坏情况下 s 能有多少种切割呢？长度为 N 的字符串 s 中共有 N - 1 个「缝隙」可供切割，每个缝隙可以选择「切」或者「不切」，所以 s 最多有 O(2^N) 种切割方式，即递归树上最多有 O(2^N) 个节点。

当然，实际情况可定会好一些，毕竟存在剪枝逻辑，但从最坏复杂度的角度来看，递归树的节点个数确实是指数级别的。

那么 backtrack 函数本身的时间复杂度是多少呢？主要的时间消耗是遍历 wordDict 寻找匹配 s[i..] 的前缀的单词：

// 遍历 wordDict 的所有单词
for (String word : wordDict) {
    // 看看哪个单词能够匹配 s[i..] 的前缀
    int len = word.length();
    if (i + len <= s.length()
        && s.substring(i, i + len).equals(word)) {
        // 找到一个单词匹配 s[i..i+len)
        // ...
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 遍历 wordDict 的所有单词
for (string word : wordDict) {
    // 看看哪个单词能够匹配 s[i..] 的前缀
    int len = word.length();
    if (i + len <= s.length()
        && s.substr(i, len) == word) {
        // 找到一个单词匹配 s[i..i+len)
        // ...
    }
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

# 遍历 wordDict 的所有单词
for word in wordDict:
    # 看看哪个单词能够匹配 s[i..] 的前缀
    length = len(word)
    if i + length <= len(s) and s[i: i + length] == word:
        # 找到一个单词匹配 s[i..i+len)
        # ...

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

for _, word := range wordDict {
    len := len(word)
    if i+len <= len(s) && s[i:i+len] == word {
        // 找到一个单词匹配 s[i:i+len]
        // ...
    }
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

for (var i = 0; i < wordDict.length; i++) {
    var word = wordDict[i];
    var len = word.length;
    if (i + len <= s.length 
        && s.substring(i, i + len) === word) {
        // 找到一个单词匹配 s[i..i+len)
        // ...
    }
}

设 wordDict 的长度为 M，字符串 s 的长度为 N，那么这段代码的最坏时间复杂度是 O(MN)（for 循环 O(M)，Java 的 substring 方法 O(N)），所以总的时间复杂度是 O(2^N * MN)。

这里顺便说一个细节优化，其实你也可以反过来，通过穷举 s[i..] 的前缀去判断 wordDict 中是否有对应的单词：

// 注意，要转化成哈希集合，提高 contains 方法的效率
HashSet<String> wordDict = new HashSet<>(wordDict);

// 遍历 s[i..] 的所有前缀
for (int len = 1; i + len <= s.length(); len++) {
    // 看看 wordDict 中是否有单词能匹配 s[i..] 的前缀
    String prefix = s.substring(i, i + len);
    if (wordDict.contains(prefix)) {
        // 找到一个单词匹配 s[i..i+len)
        // ...
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 注意，要转换为 unordered_set，提高 count 方法的效率
unordered_set<string> wordDict(wordDict.begin(), wordDict.end()); 

// 遍历 s[i..] 的所有前缀
for (int len = 1; i + len <= s.length(); len++) {
    // 看看 wordDict 中是否有单词能匹配 s[i..] 的前缀
    string prefix = s.substr(i, len);
    if (wordDict.count(prefix)) {
        // 找到一个单词匹配 s[i..i+len)
        // ...
    }
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

# 注意，要转化成哈希集合，提高 contains 方法的效率
wordDict = set(wordDict)

# 遍历 s[i..] 的所有前缀
for length in range(1, len(s)-i+1):
    # 看看 wordDict 中是否有单词能匹配 s[i..] 的前缀
    prefix = s[i:i+length]
    if prefix in wordDict:
        # 找到一个单词匹配 s[i..i+len)
        # ...

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 注意，要转化成哈希集合，提高 contains 方法的效率
wordDict := make(map[string]bool)
for _, word := range wordDict {
    wordDict[word] = true
}

// 遍历 s[i..] 的所有前缀
for len := 1; i+len <= len(s); len++ {
    // 看看 wordDict 中是否有单词能匹配 s[i..] 的前缀
    prefix := s[i:i+len]
    if wordDict[prefix] {
        // 找到一个单词匹配 s[i..i+len)
        // ...
    }
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var wordDict = new Set(wordDict);

for (var len = 1; i + len <= s.length; len++) {
    var prefix = s.substring(i, i + len);
    if (wordDict.has(prefix)) {
        // 找到一个单词匹配 s[i..i+len)
        // ...
    }
}

这段代码和刚才那段代码的结果是一样的，但这段代码的时间复杂度变成了 O(N^2)，和刚才的代码不同。

到底哪样子好呢？这要看题目给的数据范围。本题说了 1 <= s.length <= 300, 1 <= wordDict.length <= 1000，所以 O(N^2) 的结果较小，这段代码的实际运行效率应该稍微高一些，这个是一个细节的优化，你可以自己做一下，我就不写了。

不过即便你优化这段代码，总的时间复杂度依然是指数级的 O(2^N * N^2)，是无法通过所有测试用例的，那么问题出在哪里呢？

比如输入 wordDict = ["a", "aa"], s = "aaab"，算法无法找到一个可行的组合，所以一定会遍历整棵回溯树，但你注意这里面会存在重复的情况：

图中标红的这两部分，虽然经历了不同的切分，但是切分得出的结果是相同的，所以这两个节点下面的子树也是重复的，即存在冗余计算，极端情况下会消耗大量时间。

如何消除冗余计算呢？这就要稍微转变一下思维模式，用「分解问题」的思维模式来考虑这道题。

我们刚才以排列组合的视角思考这个问题，现在我们换一种视角，思考一下是否能够把原问题分解成规模更小，结构相同的子问题，然后通过子问题的结果计算原问题的结果。

对于输入的字符串 s，如果我能够从单词列表 wordDict 中找到一个单词匹配 s 的前缀 s[0..k]，那么只要我能拼出 s[k+1..]，就一定能拼出整个 s。换句话说，我把规模较大的原问题 wordBreak(s[0..]) 分解成了规模较小的子问题 wordBreak(s[k+1..])，然后通过子问题的解反推出原问题的解。

有了这个思路就可以定义一个 dp 函数，并给出该函数的定义：

// 定义：返回 s[i..] 是否能够被拼出
int dp(String s, int i);

// 计算整个 s 是否能被拼出，调用 dp(s, 0)

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 定义：返回 s[i..] 是否能够被拼出
int dp(string s, int i);

// 计算整个 s 是否能被拼出，调用 dp(s, 0)

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

# 定义：返回 s[i..] 是否能够被拼出
def dp(s: str, i: int) -> bool:

# 计算整个 s 是否能被拼出，调用 dp(s, 0)
def canConstruct(s: str) -> bool:
    return dp(s, 0)

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// dp返回s[i:]是否能够被拼出
func dp(s string, i int) int {
    // 实现
}

// isInterleave计算是否可以通过交错t1和t2来形成s
// 调用dp(s, 0)
func isInterleave(s string, t1 string, t2 string) bool {
    // 实现
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 定义：返回 s[i..] 是否能够被拼出
function dp(s, i) {}

// 计算整个 s 是否能被拼出，调用 dp(s, 0)
var result = dp(s, 0);

有了这个函数定义，就可以把刚才的逻辑大致翻译成伪码：

List<String> wordDict;

// 定义：返回 s[i..] 是否能够被拼出
int dp(String s, int i) {
    // base case，s[i..] 是空串
    if (i == s.length()) {
        return true;
    }
    // 遍历 wordDict，看看哪些单词是 s[i..] 的前缀
    for (Strnig word : wordDict) {
        if word 是 s[i..] 的前缀 {
            int len = word.length();
            // 只要 s[i+len..] 可以被拼出，s[i..] 就能被拼出
            if (dp(s, i + len) == true) {
                return true;
            }
        }
    }
    // 所有单词都尝试过，无法拼出整个 s
    return false;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

vector<string> wordDict;

// 定义：返回 s[i..] 是否能够被拼出
int dp(string s, int i) {
    // base case，s[i..] 是空串
    if (i == s.length()) {
        return true;
    }
    // 遍历 wordDict，看看哪些单词是 s[i..] 的前缀
    for (string word : wordDict) {
        if (s.substr(i, word.length()) == word) {
            int len = word.length();
            // 只要 s[i+len..] 可以被拼出，s[i..] 就能被拼出
            if (dp(s, i + len) == true) {
                return true;
            }
        }
    }
    // 所有单词都尝试过，无法拼出整个 s
    return false;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

wordDict: List[str]

# 定义：返回 s[i..] 是否能够被拼出
def dp(s: str, i: int) -> bool:
    # base case，s[i..] 是空串
    if i == len(s):
        return True
    # 遍历 wordDict，看看哪些单词是 s[i..] 的前缀
    for word in wordDict:
        if s[i:].startswith(word):
            l = len(word)
            # 只要 s[i+l..] 可以被拼出，s[i..] 就能被拼出
            if dp(s, i+l) == True:
                return True
    # 所有单词都尝试过，无法拼出整个 s
    return False

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var wordDict []string

// 定义：返回 s[i..] 是否能够被拼出
func dp(s string, i int) bool {
    // base case，s[i..] 是空串
    if i == len(s) {
        return true
    }
    // 遍历 wordDict，看看哪些单词是 s[i..] 的前缀
    for _, word := range wordDict {
        if strings.HasPrefix(s[i:], word) {
            len := len(word)
            // 只要 s[i+len..] 可以被拼出，s[i..] 就能被拼出
            if dp(s, i+len) == true {
                return true
            }
        }
    }
    // 所有单词都尝试过，无法拼出整个 s
    return false
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var wordDict;

// 定义：返回 s[i..] 是否能够被拼出
function dp(s, i) {
    // base case，s[i..] 是空串
    if (i == s.length) {
        return true;
    }
    // 遍历 wordDict，看看哪些单词是 s[i..] 的前缀
    for (var word of wordDict) {
        if (/* word 是 s[i..] 的前缀 */) {
            var len = word.length;
            // 只要 s[i+len..] 可以被拼出，s[i..] 就能被拼出
            if (dp(s, i + len) == true) {
                return true;
            }
        }
    }
    // 所有单词都尝试过，无法拼出整个 s
    return false;
}

类似之前讲的回溯算法，dp 函数中的 for 循环也可以优化一下：

// 注意，用哈希集合快速判断元素是否存在
HashSet<String> wordDict;

// 定义：返回 s[i..] 是否能够被拼出
int dp(String s, int i) {
    // base case，s[i..] 是空串
    if (i == s.length()) {
        return true;
    }
    
    // 遍历 s[i..] 的所有前缀，看看哪些前缀存在 wordDict 中
    for (int len = 1; i + len <= s.length(); len++) {
        if wordDict 中存在 s[i..len) {
            // 只要 s[i+len..] 可以被拼出，s[i..] 就能被拼出
            if (dp(s, i + len) == true) {
                return true;
            }
        }
    }
    // 所有单词都尝试过，无法拼出整个 s
    return false;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 注意，用哈希集合快速判断元素是否存在
unordered_set<string> wordDict;

// 定义：返回 s[i..] 是否能够被拼出
int dp(string s, int i) {
    // base case，s[i..] 是空串
    if (i == s.length()) {
        return true;
    }
    
    // 遍历 s[i..] 的所有前缀，看看哪些前缀存在 wordDict 中
    for (int len = 1; i + len <= s.length(); len++) {
        if(wordDict.count(s.substr(i, len)) > 0) {
            // 只要 s[i+len..] 可以被拼出，s[i..] 就能被拼出
            if (dp(s, i + len) == true) {
                return true;
            }
        }
    }
    // 所有单词都尝试过，无法拼出整个 s
    return false;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

from typing import List

# 注意，用哈希集合快速判断元素是否存在
wordDict: List[str]

# 定义：返回 s[i..] 是否能够被拼出
def dp(s: str, i: int) -> bool:
    # base case，s[i..] 是空串
    if i == len(s):
        return True
    
    # 遍历 s[i..] 的所有前缀，看看哪些前缀存在 wordDict 中
    for length in range(1, len(s) - i + 1):
        if s[i:i+length] in set(wordDict):
            # 只要 s[i+len..] 可以被拼出，s[i..] 就能被拼出
            if dp(s, i + length) is True:
                return True
    
    # 所有单词都尝试过，无法拼出整个 s
    return False

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 注意，用哈希集合快速判断元素是否存在
var wordDict map[string]bool

// dp 函数定义：返回 s[i..] 是否能够被拼出
func dp(s string, i int) bool {
    // base case，s[i..] 是空串
    if i == len(s) {
        return true
    }

    // 遍历 s[i..] 的所有前缀，看看哪些前缀存在 wordDict 中
    for len := 1; i+len <= len(s); len++ {
        if wordDict[s[i:i+len]] {
            // 只要 s[i+len..] 可以被拼出，s[i..] 就能被拼出
            if dp(s, i+len) == true {
                return true
            }
        }
    }
    // 所有单词都尝试过，无法拼出整个 s
    return false
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 注意，用哈希集合快速判断元素是否存在
var wordDict;

// 定义：返回 s[i..] 是否能够被拼出
function dp(s, i) {
    // base case，s[i..] 是空串
    if (i === s.length) {
        return true;
    }
    
    // 遍历 s[i..] 的所有前缀，看看哪些前缀存在 wordDict 中
    for (var len = 1; i + len <= s.length; len++) {
        if (wordDict.has(s.substring(i, i + len))) {
            // 只要 s[i+len..] 可以被拼出，s[i..] 就能被拼出
            if (dp(s, i + len) === true) {
                return true;
            }
        }
    }
    // 所有单词都尝试过，无法拼出整个 s
    return false;
}

对于这个 dp 函数，指针 i 的位置就是「状态」，所以我们可以通过添加备忘录的方式优化效率，避免对相同的子问题进行冗余计算。最终的解法代码如下：

class Solution {
    // 用哈希集合方便快速判断是否存在
    HashSet<String> wordDict;
    // 备忘录，-1 代表未计算，0 代表无法凑出，1 代表可以凑出
    int[] memo;

    // 主函数
    public boolean wordBreak(String s, List<String> wordDict) {
        // 转化为哈希集合，快速判断元素是否存在
        this.wordDict = new HashSet<>(wordDict);
        // 备忘录初始化为 -1
        this.memo = new int[s.length()];
        Arrays.fill(memo, -1);
        return dp(s, 0);
    }

    // 定义：s[i..] 是否能够被拼出
    boolean dp(String s, int i) {
        // base case
        if (i == s.length()) {
            return true;
        }
        // 防止冗余计算
        if (memo[i] != -1) {
            return memo[i] == 0 ? false : true;
        }

        // 遍历 s[i..] 的所有前缀
        for (int len = 1; i + len <= s.length(); len++) {
            // 看看哪些前缀存在 wordDict 中
            String prefix = s.substring(i, i + len);
            if (wordDict.contains(prefix)) {
                // 找到一个单词匹配 s[i..i+len)
                // 只要 s[i+len..] 可以被拼出，s[i..] 就能被拼出
                boolean subProblem = dp(s, i + len);
                if (subProblem == true) {
                    memo[i] = 1;
                    return true;
                }
            }
        }
        // s[i..] 无法被拼出
        memo[i] = 0;
        return false;
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class Solution {
private:
    // 用哈希集合方便快速判断是否存在
    unordered_set<string> wordDict;
    // 备忘录，-1 代表未计算，0 代表无法凑出，1 代表可以凑出
    vector<int> memo;

public:
    // 主函数
    bool wordBreak(string s, vector<string>& wordDict) {
        // 转化为哈希集合，快速判断元素是否存在
        for (auto word : wordDict) {
            this->wordDict.insert(word);
        }
        // 备忘录初始化为 -1
        memo.resize(s.length(), -1);
        return dp(s, 0);
    }

    // 定义：s[i..] 是否能够被拼出
    bool dp(const string& s, int i) {
        // base case
        if (i == s.length()) {
            return true;
        }
        // 防止冗余计算
        if (memo[i] != -1) {
            return memo[i] == 0 ? false : true;
        }

        // 遍历 s[i..] 的所有前缀
        for (int len = 1; i + len <= s.length(); len++) {
            // 看看哪些前缀存在 wordDict 中
            string prefix = s.substr(i, len);
            if (wordDict.count(prefix)) {
                // 找到一个单词匹配 s[i..i+len)
                // 只要 s[i+len..] 可以被拼出，s[i..] 就能被拼出
                bool subProblem = dp(s, i + len);
                if (subProblem == true) {
                    memo[i] = 1;
                    return true;
                }
            }
        }
        // s[i..] 无法被拼出
        memo[i] = 0;
        return false;
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

from typing import List

class Solution:
    # 用哈希集合方便快速判断是否存在
    def __init__(self):
        self.wordDict = set()
        # 备忘录，-1 代表未计算，0 代表无法凑出，1 代表可以凑出
        self.memo = []

    # 主函数
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # 转化为哈希集合，快速判断元素是否存在
        self.wordDict = set(wordDict)
        # 备忘录初始化为 -1
        self.memo = [-1 for _ in range(len(s))]
        return self.dp(s, 0)

    # 定义：s[i..] 是否能够被拼出
    def dp(self, s: str, i: int) -> bool:
        # base case
        if i == len(s):
            return True
        # 防止冗余计算
        if self.memo[i] != -1:
            return False if self.memo[i] == 0 else True

        # 遍历 s[i..] 的所有前缀
        for length in range(1, len(s) - i + 1):
            # 看看哪些前缀存在 wordDict 中
            prefix = s[i: i + length]
            if prefix in self.wordDict:
                # 找到一个单词匹配 s[i..i+len)
                # 只要 s[i+len..] 可以被拼出，s[i..] 就能被拼出
                sub_problem = self.dp(s, i + length)
                if sub_problem == True:
                    self.memo[i] = 1
                    return True

        # s[i..] 无法被拼出
        self.memo[i] = 0
        return False

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func wordBreak(str string, wordDict []string) bool {
    // 用哈希集合方便快速判断是否存在
    wordDictMap := make(map[string]bool)
    for _, word := range wordDict {
        wordDictMap[word] = true
    }
    // 备忘录，-1 代表未计算，0 代表无法凑出，1 代表可以凑出
    memo := make([]int, len(str))
    for i := 0; i < len(memo); i++ {
        memo[i] = -1
    }
    return dp(str, 0, wordDictMap, memo)
}

// 定义：s[i..] 是否能够被拼出
func dp(str string, i int, wordDictMap map[string]bool, memo []int) bool {
    // base case
    if i == len(str) {
        return true
    }
    // 防止冗余计算
    if memo[i] != -1 {
        return memo[i] == 0 ? false : true
    }

    // 遍历 s[i..] 的所有前缀
    for len := 1; i+len <= len(str); len++ {
        // 看看哪些前缀存在 wordDict 中
        prefix := str[i : i+len]
        if _, ok := wordDictMap[prefix]; ok {
            // 找到一个单词匹配 s[i..i+len)
            // 只要 s[i+len..] 可以被拼出，s[i..] 就能被拼出
            subProblem := dp(str, i+len, wordDictMap, memo)
            if subProblem {
                memo[i] = 1
                return true
            }
        }
    }
    // s[i..] 无法被拼出
    memo[i] = 0
    return false
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var wordBreak = function(s, wordDict) {
    // 用哈希集合方便快速判断是否存在
    let wordSet = new Set(wordDict);
    // 备忘录，-1 代表未计算，0 代表无法凑出，1 代表可以凑出
    let memo = Array(s.length).fill(-1);

    // 主函数
    function dp(i) {
        // base case
        if (i == s.length)
            return true;
        // 防止冗余计算
        if (memo[i] !== -1)
            return memo[i] == 0 ? false : true;

        // 遍历 s[i..] 的所有前缀
        for (let j = i + 1; j <= s.length; j++) {
            // 看看哪些前缀存在 wordDict 中
            let prefix = s.substring(i, j);
            if (wordSet.has(prefix) && dp(j)) {
                // 找到一个单词匹配 s[i..i+len)
                // 只要 s[j..] 可以被拼出，s[i..] 就能被拼出
                memo[i] = 1;
                return true;
            }
        }

        // s[i..] 无法被拼出
        memo[i] = 0;
        return false;
    }

    return dp(0);
};

这个解法能够通过所有测试用例，我们根据算法时空复杂度使用指南来算一下它的时间复杂度：

因为有备忘录的辅助，消除了递归树上的重复节点，使得递归函数的调用次数从指数级别降低为状态的个数 O(N)，函数本身的复杂度还是 O(N^2)，所以总的时间复杂度是 O(N^3)，相较回溯算法的效率有大幅提升。

单词拆分 II

有了上一道题的铺垫，力扣第 140 题「单词拆分 IIopen in new window」就容易多了，先看下题目：

相较上一题，这道题不是单单问你 s 是否能被拼出，还要问你是怎么拼的，其实只要把之前的解法稍微改一改就可以解决这道题。

上一道题的回溯算法维护一个 found 变量，只要找到一种拼接方案就提前结束遍历回溯树，那么在这道题中我们不要提前结束遍历，并把所有可行的拼接方案收集起来就能得到答案：

class Solution {
    // 记录结果
    List<String> res = new LinkedList<>();
    // 记录回溯算法的路径
    LinkedList<String> track = new LinkedList<>();
    List<String> wordDict;

    // 主函数
    public List<String> wordBreak(String s, List<String> wordDict) {
        this.wordDict = wordDict;
        // 执行回溯算法穷举所有可能的组合
        backtrack(s, 0);
        return res;
    }

    // 回溯算法框架
    void backtrack(String s, int i) {
        // base case
        if (i == s.length()) {
            // 找到一个合法组合拼出整个 s，转化成字符串
            res.add(String.join(" ", track));
            return;
        }

        // 回溯算法框架
        for (String word : wordDict) {
            // 看看哪个单词能够匹配 s[i..] 的前缀
            int len = word.length();
            if (i + len <= s.length()
                && s.substring(i, i + len).equals(word)) {
                // 找到一个单词匹配 s[i..i+len)
                // 做选择
                track.addLast(word);
                // 进入回溯树的下一层，继续匹配 s[i+len..]
                backtrack(s, i + len);
                // 撤销选择
                track.removeLast();
            }
        }
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class Solution {
public:
    // 记录结果
    vector<string> res;
    // 记录回溯算法的路径
    vector<string> track;
    vector<string> wordDict;

    // 主函数
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        this->wordDict = wordDict;
        // 执行回溯算法穷举所有可能的组合
        backtrack(s, 0);
        return res;
    }

    // 回溯算法框架
    void backtrack(string s, int i) {
        // base case
        if (i == s.size()) {
            // 找到一个合法组合拼出整个 s，转化成字符串
            string temp = "";
            for(int k = 0; k < track.size(); k++){
                temp += track[k];
                if(k != track.size()-1){
                    temp += " ";
                }
            }
            res.push_back(temp);
            return;
        }

        // 回溯算法框架
        for (auto word : wordDict) {
            // 看看哪个单词能够匹配 s[i..] 的前缀
            int len = word.size();
            if (i + len <= s.size()
                && s.substr(i, len) == word) {
                // 找到一个单词匹配 s[i..i+len)
                // 做选择
                track.push_back(word);
                // 进入回溯树的下一层，继续匹配 s[i+len..]
                backtrack(s, i + len);
                // 撤销选择
                track.pop_back();
            }
        }
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

from typing import List

class Solution:
    
    def __init__(self):
        # 记录结果
        self.res = []
        # 记录回溯算法的路径
        self.track = []
        self.wordDict = []

    # 主函数
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        self.wordDict = wordDict
        # 执行回溯算法穷举所有可能的组合
        self.backtrack(s, 0)
        return self.res

    # 回溯算法框架
    def backtrack(self, s: str, i: int) -> None:
        # base case
        if i == len(s):
            # 找到一个合法组合拼出整个 s，转化成字符串
            self.res.append(' '.join(self.track))
            return

        # 回溯算法框架
        for word in self.wordDict:
            # 看看哪个单词能够匹配 s[i..] 的前缀
            length = len(word)
            if i + length <= len(s) and s[i:i+length] == word:
                # 找到一个单词匹配 s[i..i+len)
                # 做选择
                self.track.append(word)
                # 进入回溯树的下一层，继续匹配 s[i+len..]
                self.backtrack(s, i+length)
                # 撤销选择
                self.track.pop()

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func wordBreak(s string, wordDict []string) []string {
    var res []string
    var track []string
    
    // 定义回溯函数
    backtrack := func(i int) {
        // 当 i 超出字符串 s 的长度，说明找到了一种拼接方案
        if i == len(s) {
            // 将加入组合的单词列表合并成字符串，加入结果数组
            res = append(res, strings.Join(track, " "))
            return
        }
        
        // 回溯算法处理，穷举所有可能的组合
        for _, word := range wordDict {
            lenWord := len(word)
            if i + lenWord <= len(s) && s[i:i+lenWord] == word {
                // 选择该单词
                track = append(track, word)
                // 继续匹配后面的单词
                backtrack(i+lenWord)
                // 撤销选择
                track = track[:len(track)-1]
            }
        }
    }
    
    backtrack(0)
    
    return res
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

/**
 * 主函数
 * @param {string} s - 给定字符串
 * @param {string[]} wordDict - 给定的单词列表
 * @return {string[]} - 所有可拼接的字符串
 */
var wordBreak = function(s, wordDict) {
    // 存储结果
    let res = [];
    // 存储路径
    let track = [];
    backtrack(s, 0, wordDict, track, res);
    return res;
};

/**
 * 回溯函数
 * @param {string} s - 字符串
 * @param {number} i - 当前位置
 * @param {string[]} wordDict - 给定的单词列表
 * @param {string[]} track - 当前路径
 * @param {string[]} res - 存储结果
 */
var backtrack = function(s, i, wordDict, track, res) {
    // base case
    if (i === s.length) {
        // 拼接出一条新路径，加入结果
        res.push(track.join(" "));
        return;
    }
    for (let word of wordDict) {
        let len = word.length;
        if (i + len <= s.length && s.substring(i, i + len) === word) {
            // 选择该单词
            track.push(word);
            // 继续往下遍历
            backtrack(s, i + len, wordDict, track, res);
            // 撤销选择
            track.pop();
        }
    }
};

这个解法的时间复杂度和前一道题类似，依然是 O(2^N * MN)，但由于这道题给的数据规模较小，所以可以通过所有测试用例。

类似的，这个问题也可以用分解问题的思维解决，把上一道题的 dp 函数稍作修改即可：

class Solution {
    HashSet<String> wordDict;
    // 备忘录
    List<String>[] memo;

    public List<String> wordBreak(String s, List<String> wordDict) {
        this.wordDict = new HashSet<>(wordDict);
        memo = new List[s.length()];
        return dp(s, 0);
    }



    // 定义：返回用 wordDict 构成 s[i..] 的所有可能
    List<String> dp(String s, int i) {
        List<String> res = new LinkedList<>();
        if (i == s.length()) {
            res.add("");
            return res;
        }
        // 防止冗余计算
        if (memo[i] != null) {
            return memo[i];
        }
        
        // 遍历 s[i..] 的所有前缀
        for (int len = 1; i + len <= s.length(); len++) {
            // 看看哪些前缀存在 wordDict 中
            String prefix = s.substring(i, i + len);
            if (wordDict.contains(prefix)) {
                // 找到一个单词匹配 s[i..i+len)
                List<String> subProblem = dp(s, i + len);
                // 构成 s[i+len..] 的所有组合加上 prefix 
                // 就是构成构成 s[i] 的所有组合
                for (String sub : subProblem) {
                    if (sub.isEmpty()) {
                        // 防止多余的空格
                        res.add(prefix);
                    } else {
                        res.add(prefix + " " + sub);
                    }
                }
            }
        }
        // 存入备忘录
        memo[i] = res;
        
        return res;
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class Solution {
public:
    unordered_set<string> wordDict;
    // 备忘录
    vector<string> memo[1001];

    vector<string> wordBreak(string s, vector<string>& wordDict) {
        for (int i = 0; i < wordDict.size(); i++) {
            this->wordDict.insert(wordDict[i]);
        }
        return dp(s, 0);
    }

    // 定义：返回用 wordDict 构成 s[i..] 的所有可能
    vector<string> dp(string s, int i) {
        vector<string> res;
        if (i == s.size()) {
            res.push_back("");
            return res;
        }
        // 防止冗余计算
        if (!memo[i].empty()) {
            return memo[i];
        }

        // 遍历 s[i..] 的所有前缀
        for (int len = 1; i + len <= s.size(); len++) {
            // 看看哪些前缀存在 wordDict 中
            string prefix = s.substr(i, len);
            if (wordDict.count(prefix)) {
                // 找到一个单词匹配 s[i..i+len)
                vector<string> subProblem = dp(s, i + len);
                // 构成 s[i+len..] 的所有组合加上 prefix
                // 就是构成构成 s[i] 的所有组合
                for (string sub : subProblem) {
                    if (sub.empty()) {
                        // 防止多余的空格
                        res.push_back(prefix);
                    } else {
                        res.push_back(prefix + " " + sub);
                    }
                }
            }
        }
        // 存入备忘录
        memo[i] = res;

        return res;
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

from typing import List, Dict
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        wordDict = set(wordDict)
        memo = [None] * len(s)
        return self.dp(s, 0, wordDict, memo)

    # 定义：返回用 wordDict 构成 s[i..] 的所有可能
    def dp(self, s: str, i: int, wordDict: set, memo: List[Dict[int, List[str]]]) -> List[str]:
        res = []
        if i == len(s):
            res.append("")
            return res
        # 防止冗余计算
        if memo[i] is not None:
            return memo[i]

        # 遍历 s[i..] 的所有前缀
        for j in range(i + 1, len(s) + 1):
            # 看看哪些前缀存在 wordDict 中
            prefix = s[i:j]
            if prefix in wordDict:
                # 找到一个单词匹配 s[i..i+j)
                sub_problem = self.dp(s, j, wordDict, memo)
                # 构成 s[i+j..] 的所有组合加上 prefix 
                # 就是构成构成 s[i] 的所有组合
                for sub in sub_problem:
                    if sub == "":
                        # 防止多余的空格
                        res.append(prefix)
                    else:
                        res.append(prefix + " " + sub)

        # 存入备忘录
        memo[i] = res

        return res

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func wordBreak(s string, wordDict []string) []string {
    // 集合快速查询
    wordSet := make(map[string]bool)
    for _, word := range wordDict {
        wordSet[word] = true
    }
    // 备忘录
    memo := make([]*list.List, len(s))

    // 定义一个下标从 i 开始的子串可以被拆分成符合条件的字符串的集合
    var dp func(i int) *list.List
    dp = func(i int) *list.List {
        // 如果在最后一个下标后面，就返回一个空字符串
        if i == len(s) {
            res := list.New()
            res.PushBack("")
            return res
        }
        // 如果这个下标的状态已经被计算过了，则直接返回
        if memo[i] != nil {
            return memo[i]
        }
        res := list.New()
        for len := 1; i+len <= len(s); len++ {
            // 取到这个下标开始的子串
            sub := s[i : i+len]
            // 如果这个子串在字典里，则递归调用找到字符串集合中剩下的组合
            if wordSet[sub] {
                subProblem := dp(i+len)
                for e := subProblem.Front(); e != nil; e = e.Next() {
                    // 在前面加入这个子串
                    str := e.Value.(string)
                    if str == "" {
                        res.PushBack(sub)
                    } else {
                        res.PushBack(sub + " " + str)
                    }
                }
            }
        }
        // 将结果存入 memo，返回这个下标的字符串集合
        memo[i] = res
        return res
    }

    // 最终返回从 0 开始的字符串集合
    var res []string
    for e := dp(0).Front(); e != nil; e = e.Next() {
        res = append(res, e.Value.(string))
    }
    return res
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var wordBreak = function(s, wordDict) {
    const wordDictSet = new Set(wordDict);
    // 备忘录
    const memo = new Map();
    
    // 定义：返回用 wordDict 构成 s[i..] 的所有可能
    const dp = (i) => {
        const res = [];
        if (i === s.length) {
            res.push("");
            return res;
        }
        // 防止冗余计算
        if (memo.has(i)) {
            return memo.get(i);
        }
        
        // 遍历 s[i..] 的所有前缀
        for (let j = i + 1; j <= s.length; j++) {
            // 看看哪些前缀存在 wordDict 中
            const prefix = s.slice(i, j);
            if (wordDictSet.has(prefix)) {
                // 找到一个单词匹配 s[i..i+len)
                const suffixList = dp(j);
                // 构成 s[i+len..] 的所有组合加上 prefix 
                // 就是构成构成 s[i] 的所有组合
                suffixList.forEach((suffix) => {
                    const space = suffix === "" ? "" : " ";
                    res.push(prefix + space + suffix);
                });
            }
        }
        // 存入备忘录
        memo.set(i, res);
        
        return res;
    };
    
    return dp(0);
};

这个解法依然用备忘录消除了重叠子问题，所以 dp 函数递归调用的次数减少为 O(N)，但 dp 函数本身的时间复杂度上升了，因为 subProblem 是一个子集列表，它的长度是指数级的。再加上 Java 中用 + 拼接字符串的效率并不高，且还要消耗备忘录去存储所有子问题的结果，所以这个算法的时间复杂度并不比回溯算法低，依然是指数级别。

综上，我们处理排列组合问题时一般使用回溯算法去「遍历」回溯树，而不用「分解问题」的思路去处理，因为存储子问题的结果就需要大量的时间和空间，除非重叠子问题的数量较多的极端情况，否则得不偿失。

以上就是本文的全部内容，希望你能对回溯思路和分解问题的思路有更深刻的理解。

《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复「全家桶」可下载配套 PDF 和刷题全家桶：

共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释

# 单词拆分 I

# 单词拆分 II

单词拆分 I

单词拆分 II