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)