果然,它确实给我一种之前下一个排列的味道,那么再去看看这道题,深化树和排列组合之间的关系
这里我原本的做法就是类似枚举,最后是几个数字几个答案
主要用到的是中途更新的做法,比如一开始是 abc,之后的 ad ae af,这样重新装作是一个新的组,他们还是要参与后面的首部
听不听得懂随便吧
回溯法
这里视频提到了一个观点,之前我好像有注意到,就是有时候很难暴力,因为暴力的循环嵌套数是一个参数
比如输出长度 2 的 (其实就是本题电话号码的字母组合) 字符串,每个字符要在一个集合中取
容易想到两层循环,每层遍历集合,两层是因为长度 2
那输出长度为 3 呢?是参数呢?循环的嵌套数是不能动态表示的,所以有了回溯 (吗)
子集型回溯
不知道是不是回溯就是和递归有关系,如果和递归有关系,就要考虑原问题和子问题
现在是构造一个长度为 n 的字符串,枚举完第一个字符就是构造 n-1 的字符串了
增量构造答案,视频里提到了这个词,就是我说的很像 下一个排列 里的画树