1. 216.组合总和III
这个的剪枝有两步,一步是当前和如果直接比n大就直接返回
另一个就有点抽象,i<=9变成i<=9-(k-path.length)+1
,这个理解起来就是倒着看,比如k=3,我现在已经添了一个数进path,那我还需要2个数,也就是k-1
,那i最大能取到哪里呢?还需要两个数的话,你最大只能是8,因为[8,9]有两个元素,再少k的个数就不够了,但是9-(k-length)
是前一位,比如9-(3-1)=7,我们最大可以取8.
2. 17.电话号码的字母组合
这题不难,但是坑很多.
要先解决映射问题:
建好对应的map数组.判断返回条件的时候,要用
join(“”)
把数组拼接起来.-
每次循环这里是用的
const v of map[digits[i]]
回溯抽象成的树的宽度就是代表的字符串的长度,一个数字代表三个,那数的宽度就是3.回溯抽象成的树的深度就是输入的字符的长度,输入5个就要从第一个字符里取,再第二个字符里取,...
这题往递归函数里传的i是index,而不是startIndex,startIndex是在同一个集合里,告诉我们现在到哪了,之前遍历了哪些元素.但是index是在两个集合或者多个集合里,做一个组合