代码随想录算法训练营第19天

77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

class Solution:def combine(self, n: int, k: int) -> List[List[int]]:path = []res = []def dfs(n,k,index):if len(path) ==k:res.append(path[:])returnfor i in range(index,n+1):path.append(i)dfs(n,k,i+1)path.pop()dfs(n,k,1)return res

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次 

class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:path = []res = []def dfs(k,n,s,index):if len(path) ==k:if s == n:res.append(path[:])returnfor i in range(index,10):if s + i > n:breakpath.append(i)s += idfs(k,n,s,i+1)path.pop()s -=idfs(k,n,0,1)return res

17. 电话号码的字母组合

class Solution:def letterCombinations(self, digits: str) -> List[str]:hash = {'0':'','1':'','2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}path = ''res = []def dfs(digits,index,path):if index == len(digits):res.append(path[:])returns = hash[digits[index]]for i in range(len(s)):path += s[i]dfs(digits,index + 1,path)path = path[:-1]if len(digits)==0:return []dfs(digits,0,path)return res