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