LeetCode 216. 组合总和 III | Python

大梦三千秋 2020/9/12 8:03:41

216. 组合总和 III 题目来源:力扣(LeetCode)https://leetcode-cn.com/problems/combination-sum-iii 题目 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。 说明: 所有数字都是正整数。 解集不能包含重复的…

216. 组合总和 III


题目来源:力扣(LeetCode)https://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. 组合总和 II

其中本题与第 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
随时随地学软件编程-关注百度小程序和微信小程序
关于找一找教程网

本站文章仅代表作者观点,不代表本站立场,所有文章非营利性免费分享。
本站提供了软件编程、网站开发技术、服务器运维、人工智能等等IT技术文章,希望广大程序员努力学习,让我们用科技改变世界。
[LeetCode 216. 组合总和 III | Python]http://www.zyiz.net/tech/detail-146952.html

上一篇:如何在Python中使用eval ?

下一篇:Selenium3与Python3实战Web自动化测试框架【日记1】

赞(0)

共有 条评论 网友评论

验证码: 看不清楚?
    关注微信小程序
    程序员编程王-随时随地学编程

    扫描二维码或查找【程序员编程王】

    可以随时随地学编程啦!

    技术文章导航 更多>
    扫一扫关注最新编程教程