回溯

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/?envType=problem-list-v2&envId=backtracking

果然,它确实给我一种之前下一个排列的味道,那么再去看看这道题,深化树和排列组合之间的关系

这里我原本的做法就是类似枚举,最后是几个数字几个答案

主要用到的是中途更新的做法,比如一开始是 abc,之后的 ad ae af,这样重新装作是一个新的组,他们还是要参与后面的首部

听不听得懂随便吧

回溯法

这里视频提到了一个观点,之前我好像有注意到,就是有时候很难暴力,因为暴力的循环嵌套数是一个参数

比如输出长度 2 的 (其实就是本题电话号码的字母组合) 字符串,每个字符要在一个集合中取

容易想到两层循环,每层遍历集合,两层是因为长度 2

那输出长度为 3 呢?是参数呢?循环的嵌套数是不能动态表示的,所以有了回溯 (吗)

子集型回溯

不知道是不是回溯就是和递归有关系,如果和递归有关系,就要考虑原问题和子问题

现在是构造一个长度为 n 的字符串,枚举完第一个字符就是构造 n-1 的字符串了

增量构造答案,视频里提到了这个词,就是我说的很像 下一个排列 里的画树