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

欢送关注

公众号【书所集录】