216.组合总和III
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。
思路:由于1-9每个数只能用一次,那就定义回溯函数backtrack(start, path, target),for循环从range(start, 10)里选 i, 下一层backtrack(i+1, path, target-i)。
剪枝:1. 到长度了,不管和对不对,都要停止。2. 如果剩下的数都比target大,那也要停止。3. 因为要k个数,因此 i 不能超过10-(k - lenth)
17.电话号码的字母组合
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
以下是卡哥资料:
216.组合总和III
如果把 组合问题理解了,本题就容易一些了。
题目链接/文章讲解:https://programmercarl.com/0216.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CIII.html
视频讲解:https://www.bilibili.com/video/BV1wg411873x
17.电话号码的字母组合
本题大家刚开始做会有点难度,先自己思考20min,没思路就直接看题解。