216. 组合总和III
题目简述
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
思路
回溯
class Solution: def combinationSum3(self, k: int, n: int) -> List[List[int]]: res=[] def backtrack(list,add,depth,change_list): if depth==k: if add==n: res.append([j for j in change_list]) return for i in range(len(list)): add+=list[i] depth+=1 change_list.append(list[i]) if add<=n: backtrack(list[i+1:],add,depth,change_list) change_list.pop() depth-=1 add-=list[i] else: # list数据类型一定要pop，不pop，return后change_list并不会变成原来那样 change_list.pop() return nums=[1,2,3,4,5,6,7,8,9] backtrack(nums,0,0,[]) return res
17. 电话号码的字母组合
题目简述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
思路
回溯
class Solution: def letterCombinations(self, digits: str) -> List[str]: dict={ "2":['a','b','c'], "3":['d','e','f'], "4":['g','h','i'], "5":['j','k','l'], "6":['m','n','o'], "7":['p','q','r','s'], "8":['t','u','v'], "9":['w','x','y','z'] } list=[] ll=len(digits) if not ll: return list def backtrack(length,res,index): if length==ll: list.append(''.join(j for j in res)) return for i in dict[digits[index]]: res.append(i) length+=1 backtrack(length,res,index+1) length-=1 res.pop() backtrack(0,[],0) return list