组合总和III

Leetcode Link: 216. 组合总和 III - 力扣（LeetCode）

题目

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9 每个数字 最多使用一次  返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

解法一

思路：回溯 本题的回溯终止条件有下面几个：

1. 当前路径内的点超过 k（题目要求等于 k，再多了没用）
2. 目标值小于 0（因为给的候选都是 >0 的）
3. 获取了题目要求的结果，同样可以终止回溯，因为再往下走路径就会 >k ，我们不需要。

本题是组合，所以新的choose是当前值往后的所有

题解：

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        def backtracking(tar, choose):
            nonlocal k
            # 回溯终止条件
            if tar <= 0 or len(path) > k: 
                return
			# 开始递归回溯
            for idx, val in enumerate(choose):
                path.append(val)
				# 题目满足条件
				# 恰好也是回溯终止条件，因为不需要更多的数字了
                if val == tar and len(path)==k:
                    res.append(copy.deepcopy(path))
                    path.pop()
                    return 
                # 注意更新目标值以及choose
                backtracking(tar - val, choose[idx+1:])
                path.pop()
            
        path = []
        res = []
        choose = [x for x in range(1, 10)]
        target = n
        backtracking(n, choose)
        return res

考虑剪枝，当 len (path) + len (choose[idx+1:]) < k 的就可以不看了 其实回溯终止条件 (1 或者 (2 都可以算作一个剪枝

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        def backtracking(tar, choose):
            nonlocal k
            # 回溯终止条件
            if tar <= 0 or len(path) > k: 
                return
			# 开始递归回溯
            for idx, val in enumerate(choose):
                path.append(val)
				# 题目满足条件
				# 恰好也是回溯终止条件，因为不需要更多的数字了
                if val == tar and len(path)==k:
                    res.append(copy.deepcopy(path))
                    path.pop()
                    return 
				# 剪枝
				if len(path)+len(choose[idx+1:]) < k:
                    path.pop() #！一定记得pop
                    return
 
                # 注意更新目标值以及choose
                backtracking(tar - val, choose[idx+1:])
                path.pop()
            
        path = []
        res = []
        choose = [x for x in range(1, 10)]
        target = n
        backtracking(n, choose)
        return res

启发和联系