子集求和问题--如何在多项式时间内验证“假”情况？

子集求和问题（Subset Sum Problem）是一个经典的 NP 完全问题，给定整数集合 S 和一个整数 t，判断是否存在 S 的一个子集的和等于 t。

验证 Subset Sum 问题的“假”情况，即给出证据证明无解，可以通过构造算法按照以下步骤进行：

1. 遍历整数集合 S，如果 t 小于 S 中最小的整数，直接返回 false。

2. 将整数集合 S 按升序排序。

3. 初始化一个布尔类型数组 dp，长度为 t+1，全部元素初始化为 false。dp[j] 表示是否存在 S 的一个子集的和等于 j。

4. 将 dp[0] 设为 true，表示存在 S 的一个子集的和等于 0（即不选任何数）。

5. 遍历整数集合 S，对于每个整数 num，从后往前遍历数组 dp，如果 dp[j-num] 为 true（表示存在一个子集的和为 j-num），将 dp[j] 设为 true。

6. 最终，如果 dp[t] 为 false，则无解；如果 dp[t] 为 true，则有解。

代码实现如下：

def subset_sum(S, t):
    if t < min(S):
        return False
    S.sort()
    dp = [False] * (t+1)
    dp[0] = True
    for num in S:
        for j in range(t, num-1, -1):
            if dp[j-num]:
                dp[j] = True
    return dp[t]