Python中的回溯法和剪枝的应用：求数组中满足给定目标所有的子数组

假定给定数组 nums = [2, 3, 4, 6, 8, 9] ，目标值为 4 ，求目标和等于 4 的所有子数组的组合，具体如下所示：

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

# 所有组合
[2, 2]
[4]

现在用回溯法和剪枝求出所有的满足特定目标的组合，这里我们采用的是加法，即采用这里的思想。

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

def track(index, num):    

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

        num.append(nums[i])

        if sum(num) < n:   # 不断回溯
            track(i, num)
        elif sum(num) == n:# 输出符合的结果
            print(num)
        
        num.pop()

track(0, [])

输出：

[2, 2, 2, 3]     
[2, 3, 4]        
[3, 3, 3]        
[3, 6]
[9]