Python中的回溯法和剪枝的应用：求数组中满足目标的

假定给定升序的整数列表 nums = [1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9]，给定的目标为 11，参考上一篇的思路，则子数组和为 11 共有下面那么多组合：

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2]
[1, 1, 1, 1, 1, 1, 1, 1, 3]

........

[1, 4, 6]
[1, 4, 6]
[1, 5, 5]
[2, 2, 2, 2, 3]
[2, 2, 2, 2, 3]
[2, 2, 2, 5]
[2, 2, 2, 2, 3]
[2, 2, 2, 5]
[2, 2, 3, 4]
[2, 2, 7]

.......

[2, 3, 3, 3]
[2, 3, 6]
[2, 4, 5]
[2, 4, 5]
[2, 9]
[3, 3, 5]
[3, 4, 4]
[3, 4, 4]
[3, 8]
[4, 7]
[4, 7]
[5, 6]

在上一篇的要求中，我们没有要求每一种元素重复使用几次，所以才会产生那么多种组合，对此我们对回溯法和剪枝加一些限制条件，以保证每个元素只被使用一次。

方法一：加法

nums = [1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9]  # 给定数组
n = 11                                           # 目标值

def track(index, num):    

    for i in range(index, len(nums)):   # 裁剪枝叶

        if nums[i] == nums[i-1] and i > index: # 当前的循环中 同一元素不能出现2次
            continue                           # 主要依靠 i > index 实现

        if sum(num + [nums[i]]) < n:    # 不断回溯
            track(i + 1, num + [nums[i]])

        elif sum(num + [nums[i]]) == n: # 输出符合的结果
            print(num + [nums[i]])
            return                      # 因为是升序序列，满足即可跳出此次回溯

        else:
            return                      # 不满足即可跳出此次回溯
        
track(0, [])

输出：

[1, 2, 2, 6]
[1, 2, 3, 5]
[1, 2, 4, 4]
[1, 2, 8]
[1, 3, 7]
[1, 4, 6]
[2, 2, 3, 4]
[2, 2, 7]
[2, 3, 6]
[2, 4, 5]
[2, 9]
[3, 4, 4]
[3, 8]
[4, 7]
[5, 6]

方法二：减法

nums = [1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9]  # 给定数组
m = 11                                           # 目标值
 
def track(num, index, n):
 
    for i in range(index, len(nums)):  # 裁枝
        
        if nums[i] == nums[i-1] and i > index: # 当前的循环中 同一元素不能出现2次
            continue                           # 主要依靠 i > index 实现

        if nums[i] == n:
            print(num + [nums[i]])
            return       # 因为是升序序列 后面的都不满足了
        
        elif nums[i] < n:  # 不断的回溯
            track(num + [nums[i]], i + 1, n - nums[i])
        
        else:
            return       # 因为是升序序列 后面的都不满足了
    
track([], 0, m)

输出：

[1, 2, 2, 6]
[1, 2, 3, 5]
[1, 2, 4, 4]
[1, 2, 8]
[1, 3, 7]
[1, 4, 6]
[2, 2, 3, 4]
[2, 2, 7]
[2, 3, 6]
[2, 4, 5]
[2, 9]
[3, 4, 4]
[3, 8]
[4, 7]
[5, 6]

以上需要读者自行话一些草图理解