本文主要是介绍代码随想录Day21 | Leetcode216 组合总和III、Leetcode17 电话号码的字母组合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、第一题
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。示例 3:
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。思路
代码会写了，思路写不出来。。。。
代码
class Solution:def combinationSum3(self, k, n):result = []res = []def dfs(i, s):d = k-len(res)# 等差数列,超过目标数或者剩下的全部数之和仍小于剩余需要的数s不继续递归，一定是不满足条件的if s < 0 or s > (2*i-d+1)*d//2:returnif d == 0:result.append(res.copy())returnfor j in range(i, d-1, -1):res.append(j)dfs(j-1, s-j)res.pop()def dfs1(i, s):d = k-len(res)if s < 0 or s > (2*i-d+1)*d//2:returnif d == 0:result.append(res.copy())# 不选iif i > d:dfs(i-1, s)# 选ires.append(i)dfs(i-1, s-i)res.pop()dfs1(9, n)return resultif __name__ == '__main__':test = Solution()n = [7, 9, 1]k = [3, 3, 4]for i in range(len(n)):print(test.combinationSum3(k[i], n[i]))
二、第二题
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]示例 2：
输入：digits = ""
输出：[]示例 3：
输入：digits = "2"
输出：["a","b","c"]思路
竟然能自己写出一个。。。。。。
代码
class Solution:def letterCombinations(self, digits):"""给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。示例 1：输入：digits = "23"输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]示例 2：输入：digits = ""输出：[]示例 3：输入：digits = "2"输出：["a","b","c"]"""if not digits:return []result = []res = []re = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']def dfs(s):if len(s) == 0:result.append(''.join(res))returnelse:for i in re[int(s[0])]:res.append(i)dfs(s[1:])res.pop()dfs(digits)return resultdef letterCombinations1(self, digits):if not digits:return []result = []re = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']def dfs(es, s):if len(s) == 0:result.append(es)else:for i in re[int(s[0])]:dfs(es + i, s[1:])dfs('', digits)return resultif __name__ == '__main__':test = Solution()digits = ['23', '', '2']for i in digits:print(test.letterCombinations(i))
这篇关于代码随想录Day21 | Leetcode216 组合总和III、Leetcode17 电话号码的字母组合的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
