216组合总和III

题目:找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明:所有数字都是正整数。解集不能包含重复的组合。
示例 1:输入: k = 3, n = 7输出: [[1,2,4]]

来源:https://leetcode-cn.com/problems/combination-sum-iii/

法一:自己的代码

思路:同前两个题大同小异,只是剪枝条件不同而已,这个题里面明确要求了最后得到的数组的长度,这个条件实际上就是剪枝条件

from typing import List

class Solution:

    def combinationSum3(self, k: int, n: int) -> List[List[int]]:

        results = []

        nums = [r+1 for r in range(9)]

        # a中存放生成的每个list, nums中存放用于遍历的数,

        def backtrack(a=[], nums=nums,):

            # 剪枝条件,如果长度不够,则不必判断和,直接进入下一次的遍历

            if len(a) < k:

                pass

            # 如果满足条件,则长度一定是k,只要和是n就返回值,并且直接结束下一次的遍历

            elif sum(a) == n:

                print(a)

                results.append(a)

                return

            for i,j in enumerate(nums):

                # (len(a) < k),这个条件必须有,比如输入(2,18),如果没有这个条件,

                # 就需要在上面的if语句中限制,这样限制更省时

                if (sum(a) + j <= n) & (len(a) < k):

                    backtrack( a+[j], nums[i+1:])

                # 如果if中有一个条件不满足,终止循环,因为nums中的数是由小到大排序的,

                # 第n个数不满足的话,n+1个之后的一定不满足,直接终止循环

                else:

                    break

        backtrack()

        return results

if __name__ == "__main__":

    duixiang = Solution()

    a = duixiang.combinationSum3(2, 18)

    print('u', a)

216组合总和III的相关教程结束。