LeetCode 216. 组合总和 III | Python

微信扫一扫,分享到朋友圈

LeetCode 216. 组合总和 III | Python

216. 组合总和 III

题目来源:力扣(LeetCodehttps://leetcode-cn.com/problems/combination-sum-iii

题目

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 – 9 的正整数,并且每种组合中不存在重复的数字。

说明:

  • 所有数字都是正整数。
  • 解集不能包含重复的组合。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

解题思路

思路:回溯

因为这篇题解是跟着每日一题去撰写的,最近的每日一题考察点有些重复,这里先放前两天题目的题解:

其中本题与第 39、40 题相同的有:

  • 解集不能包含重复组合,组合中元素都是正整数。

与第 40 题不同的有:

  • 组合不存在重复数字。

本题与第 39、40 题都不同的在于:

  • 限制组合的长度;
  • 组合元素只含 1~9。

由于近期考察的点有些重合,这里就不再赘述,可以查看上面的两篇题解进行了解。至于本题,根据与前面题目的不同点改变相应的策略,具体的思路可看下面的简单图示:

根据上面图示的思路,编写代码,具体如下。

class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
ans = []
tmp = []
def helper(choice, total):
"""
Args:
choice: 递归每层选取的元素
total: 组合中的元素和
"""
# 这里限制组合长度,
if len(tmp) == k:
if total == n:
ans.append(tmp[::])
return
# 限制元素和大于 n
if total > n:
return
# 组合中只允许 1-9 的正整数
for i in range(choice, 10):
total += i
tmp.append(i)
# 防止元素重复选取
# 同时避免组合重复
helper(i+1, total)
tmp.pop()
total -= i
total = 0
helper(1, total)
return ans

欢迎关注

公众号 【 书所集录

微信扫一扫,分享到朋友圈

LeetCode 216. 组合总和 III | Python

京东AI研究院获QuAC机器阅读理解竞赛冠军,EL-QA模型能力业界领先

上一篇

三槽巨兽:英伟达GeForce RTX 3090公版显卡实物曝光

下一篇

你也可能喜欢

LeetCode 216. 组合总和 III | Python

长按储存图像,分享给朋友