day25 代码随想录算法训练营 216. 组合总和 III

题目：216. 组合总和 III

我的感悟：

• 还是按照之前的套路来。
• 多了一个参数path_sum
• 应该是有两处剪枝，1处横线剪枝，1处纵向剪枝？或者说1处求和剪枝？1处范围剪枝？【疑问】

理解难点：

• 不剪枝的已经模的差不多了，剪枝的再看看

自己听了一遍写的：[未剪枝]

class Solution:
    def combinationSum3(self, k: int, sum_n: int) -> List[List[int]]:
        res = []
        path_sum = 0
        self.backtrack(k,sum_n,1,[],res,path_sum)
        return res
    
    def backtrack(self,k,sum_n,start,path,res,path_sum):
        # 退出条件
        if len(path) == k:
            if path_sum == sum_n: 
                res.append(path[:])
            return 
        
        # 核心遍历
        for i in range(start,10):
            path.append(i)
            path_sum += i
            self.backtrack(k,sum_n,i+1,path,res,path_sum)
            path_sum -= i
            path.pop()

剪枝版本：

class Solution:
    def combinationSum3(self, k: int, sum_n: int) -> List[List[int]]:
        res = []
        path_sum = 0
        self.backtrack(k,sum_n,1,[],res,path_sum)
        return res
    
    def backtrack(self,k,sum_n,start,path,res,path_sum):
        # 剪枝1
        if path_sum > sum_n:
            return
        # 退出条件
        if len(path) == k:
            if path_sum == sum_n: 
                res.append(path[:])
            return 
        
        # 核心遍历
        for i in range(start,10):
            if 10 - i < k - len(path):  # 剪枝2
                break
            path.append(i)
            path_sum += i
            self.backtrack(k,sum_n,i+1,path,res,path_sum)
            path_sum -= i
            path.pop()

代码示例：

通过截图：

扩展写法：

资料：