216. 组合总和 III

class Solution:
    def __init__(self):
        self.path = []
        self.result = []
        self.sum_ = 0
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        # 首先我们想到 多个 for 循环嵌套的 暴力解法，但是 k个for循环 无法控制这个k的次数。
        # 所以 我们想到了 类似 多叉树 递归 遍历的方法，来实现 k 个for 循环。
        # 但是 我们这里并不是 多叉树的递归，而是自上而下的 一种 按照某种分叉规则 的计算；
        
        # 这里是 组合，不用考虑顺序，分叉规则 就是 往右从大于 list元素和 的 数 继续 取，并递归；
        # 基线条件： 符合题目条件，不超长度；
        # 剪枝实现复杂度的缩减：向下剪枝，sum > 目标值； 向右剪枝：k - list已有的元素个数 = 还需要的元素个数，分叉规则 往右的添加点i 要保证至少还有（还需要的元素个数）个数字能够添加，不然向右找数字已经没有意义了。也就是最后一个有意义的添加位置在  9 - （还需要的元素个数）；但是！ 值得注意的是： 添加点i 所在的元素此时也没有被计入 元素个数，是在 i 的循环内才计入，因此，最后一个有意义的添加位置在  9 - （还需要的元素个数-1）；
        return self.combinationSum3_(k,n,1)
    def combinationSum3_(self,k,n,start_index):
        size = len(self.path)
        if size>k: return          # 向下剪枝
        if size==k:                # 基线条件
            if self.sum_ == n:
                print(self.path)
                self.result.append(self.path.copy()) # python 的可变对象特性，用一下浅拷贝。
        for i in range(start_index,10-(k-size)+1,1):    # 向右，事实上 是回溯完之后才会 向右。 原本是 for i in range(start_index,10,1): 变动的是向右剪枝。
            self.path.append(i)
            self.sum_ += i 
            # print(self.path)
            self.combinationSum3_(k,n,i+1) # 向下
            self.sum_ -= i
            self.path.pop()
        # print(self.result)
        return self.result