【蓝桥杯】搜索算法：剪枝技巧+记忆化搜索

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