【蓝桥杯】搜索算法：剪枝技巧+记忆化搜索
1. 可行性剪枝应用
1.1. 题目
题目描述：
给定一个正整数n和一个正整数目标值target，以及一个由不同正整数组成的数组nums。要求从nums中选出若干个数，每个数可以被选多次，使得这些数的和恰好等于target。问有多少种不同的组合方式？
输入：
-
第一行：n和target，表示数组长度和目标值
-
第二行：n个不同的正整数，表示数组nums
输出：
-
一个整数，表示不同的组合方式数量
示例：
输入：
3 4
1 2 3输出：
4解释：
组合方式为：
1+1+1+1
1+1+2
1+3
2+2
限制条件：
-
1 ≤ n ≤ 20
-
1 ≤ target ≤ 1000
-
1 ≤ nums[i] ≤ 1000
1.2. 分析
本题主要考察可行性剪枝在回溯算法中的应用。我们需要在搜索过程中及时排除不可能达到目标的分支，从而减少不必要的计算。
1️⃣排序数组：首先将数组排序，这样可以在搜索时按照一定顺序进行，便于剪枝
2️⃣回溯搜索：使用回溯法尝试所有可能的组合
3️⃣可行性剪枝：
-
当前和超过target时，立即返回
-
从当前元素开始尝试，避免重复组合（如1+2和2+1被视为相同）
-
剩余和无法用当前或更大的数达到时，提前终止
1.3. 代码
def combinationSum(nums, target):"""计算可以达到目标值的组合数量:param nums: 正整数数组:param target: 目标值:return: 组合数量"""nums.sort() # 排序便于剪枝result = 0 # 记录结果数量def backtrack(start, remaining):"""回溯函数:param start: 当前开始位置，避免重复组合:param remaining: 剩余需要凑的值"""nonlocal result# 可行性剪枝1：剩余值为0，找到有效组合if remaining == 0:result += 1return# 可行性剪枝2：从start开始，避免重复组合for i in range(start, len(nums)):num = nums[i]# 可行性剪枝3：当前数已经大于剩余值，后面更大的数更不可能，直接终止if num > remaining:break# 递归尝试选择当前数backtrack(i, remaining - num)backtrack(0, target)return result# 读取输入
n, target = m