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

欢送关注

公众号 【书所集录】