本文再谈一谈回溯和记忆化递归的差别

1.回溯vs记忆化递归

• 1.从思考问题的角度看，
  使用回溯法解决问题，不涉及【不断递减问题规模至出口case】，而就是直直白白地解一整个问题；使用记忆化递归，则不断递减问题规模至出口case，解决当前问题等价于解决若干个子问题
• 2.从返回值看，
  回溯无返回值，只负责在回溯树的叶子结点处将合法的结果纳入结果集，然后return；记忆化递归必须有返回值，当前问题的解需要依赖子问题的解，因此需要将子问题的解返回
• 3.从时间复杂度看，
  使用回溯法解决问题，要获取完整的解集，代码每次都得走到回溯树的叶子结点，然后将走过的路径纳入结果集，可能部分路径之前已经走过了，也仍然不可避免地需要重复再走来获得一整条完整路径，因此，【回溯是无法保存中间状态的，要获得每一个解就必须次次走到叶子结点】，时间复杂度较高O(N!)；使用记忆化递归，则可以保存中间状态，减少重复计算，时间复杂度可以优化。另外，这也可以从两种方法的返回值差异来解释：回溯函数无返回值，只负责叶子的结果结算，记录不了回溯树每一个中间结点的状态，所以走过回溯树的每一个结点都不会留下足迹，下次来到同一结点就像没有来过一样还得往下走；记忆化递归有返回值，即子问题都有对应的解，因此可以将计算过的子问题结果保存起来，减少重复计算

2.对比小结

回溯：整体解决一个问题，函数无返回值，无法储存中间结果
记忆化递归：解决一个问题=解决其子问题，函数有返回值，可以储存中间结果

而记忆化递归的逆向过程就是dp动规，显然，记忆化递归和dp是更优的方法，而回溯妥妥的就是暴力

3.例

leetcode140. 单词拆分 II

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

示例 1：
输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
"cats and dog",
"cat sand dog"
]

思路
1.回溯思路：将字典中的每一个word与s的前缀匹配，能够匹配则更新单词路径，并截取新的s通过dfs重复以上的操作。思路没错，但时间复杂度高会超时

# 回溯

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        res = []
        # 递归的dfs回溯
        def dfs(s, wordDict, temp_res):
            nonlocal res
            # 递归出口
            if not s:
                res.append(' '.join(temp_res))
                return
            
            # 递归
            for word in wordDict:
                l = len(word)
                if s[:l] == word:
                    # 修改状态
                    temp_res.append(word)
                    # dfs
                    dfs(s[l:], wordDict, temp_res)
                    # 状态恢复
                    temp_res.pop()
        dfs(s, wordDict, [])
        return res

2.记忆化递归：定义函数dfs(s, wordDict)，返回值List[str]表示s的解析结果，出口s == ''或s在字典self.d内，通过记忆中间结果避免重复计算，通过

class Solution:
    def __init__(self):
        self.d = dict()

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

        # 返回值List[str]， 出口s == ''或s在字典self.d内
        def dfs(s, wordDict):
            # 返回[]说明不可解析，返回['']说明可解析
            
            res = []
            # 出口
            if not s:
                return ['']
            if s not in self.d:
                # 比对每个单词是否匹配s的前缀，匹配则可缩小问题规模
                for word in wordDict:
                    l = len(word)
                    if s[:l] == word:
                        ans = dfs(s[l:], wordDict)
                        # 递归式
                        if ans:
                            for sentence in ans:
                                res.append(word+ ' ' + sentence)
                self.d[s] = res
            return self.d[s]
        
        result = dfs(s, wordDict)
        # 去掉最后一个空格符
        return [s[:-1] for s in result]