子集和

给定整数 $a_1,\dots,a_n$ 和目标 $T$,问是否存在下标集合 $I$ 使

选或不选

按下标 $i$ 和当前和 $s$ 递归,每一步跳过 $a_i$ 或者选上它:

朴素枚举是 $2^n$ 种组合。同一个 $(i,s)$ 会被不同的路径反复走到,缓存起来就是 动态规划:

from functools import lru_cache
def subset_sum(nums, target):
    @lru_cache(None)
    def solve(i, total):
        if i == len(nums):
            return total == target
        return solve(i+1, total) or solve(i+1, total+nums[i])
    return solve(0, 0)

剪枝

所有数都非负时,当前和 $s>T$ 以后再选只会更大,可以剪掉。有负数时这个剪枝是错的:后面的数可能把和拉回来。

更一般的做法:算出剩下的数能凑出的最大和与最小和,目标不在 $[s+\min,\ s+\max]$ 里才剪。这是 回溯 里「剪枝要先证明」的例子。

用到它的地方

• 知识库 回溯
• 知识库 动态规划

核对

这一条是文字讲解,由 AI 整理,没有可以数值核对的步骤;作者读过后才公开。