如何高效判断目标数X能否由给定正整数的和或差得到？

给定任意正整数列表与目标数X，需判断是否可通过对列表中的数进行加、减运算得到X，规则如下：

• 列表中的每个数仅能使用一次，列表可能存在重复元素；
• 可使用列表中任意数量的元素（1个至全部）；
• 只需返回True/False结果。

示例 #

输入：

input_list=[1, 7, 3]
X = 4

结果：TRUE（例如：7-3）

输入：

input_list=[1, 7, 3]
X = 50

结果：FALSE

原尝试方案及问题 #

之前参考组合求和的思路，将原列表与相反数列表拼接：

new_list = input_list+list(map(lambda x: -x, input_list))

再用列表推导式枚举所有组合判断和是否等于目标：

[seq for i in range(len(numbers), 0, -1)
 for seq in itertools.combinations(numbers, i)
 if sum(seq) == target]

但该方法存在两个核心问题：

1. 效率极低：枚举所有组合的时间复杂度是O(2^n)，当列表长度较大时完全不可用；
2. 重复计算：会出现同时选取原数和其相反数的无效情况（比如同时选1和-1，相当于没选，但规则要求至少选1个元素）。

我们可以用动态规划的方式，逐步记录所有可能得到的和，避免重复计算，时间复杂度优化到O(n*S)，其中S是所有数的总和。

思路 #

1. 初始化一个集合possible_sums，用来存储当前能得到的所有有效和；
2. 遍历列表中的每个数num：
   • 对于当前possible_sums中的每个已存在的和s，可以得到两个新的和：s + num 和 s - num；
   • 同时，当前数本身也可以作为一个单独的和（即只选这个数的情况）；
   • 将这些新的和加入到临时集合中，再合并到possible_sums里；
3. 遍历结束后，检查目标X是否在possible_sums中即可。

代码实现 #

def can_reach_target(input_list, X):
    total_sum = sum(input_list)
    # 提前判断：目标超出最大可能范围直接返回False
    if abs(X) > total_sum:
        return False
        
    possible_sums = set()
    for num in input_list:
        temp = set()
        # 基于已有和生成新的加减结果
        for s in possible_sums:
            temp.add(s + num)
            temp.add(s - num)
        # 加入单独使用当前数的情况
        temp.add(num)
        possible_sums.update(temp)
        # 提前剪枝：找到目标直接返回
        if X in possible_sums:
            return True
    return X in possible_sums

优化点说明 #

• 提前范围判断：先计算列表总和，若目标X的绝对值超过总和，直接返回False，避免无效计算；
• 中途剪枝：遍历过程中一旦发现目标已在可达成的和集合中，立即返回True，无需继续遍历；
• 集合去重：自动过滤重复的和，减少冗余计算，提升效率。

内容的提问来源于stack exchange，提问作者Иван Иваныч