带负数的有符号子集和到标准子集和的归约证明求助

首先先明确两个问题的形式化定义：

标准子集和（SUBSET SUM）：给定一组正整数$s_1,s_2,\dots,s_n$，判定是否存在${1,2,\dots,n}$的子集$A$，使得$A$对应元素之和等于正整数$T$。
有符号子集和（SIGNED SUBSET SUM）：给定一组可正可负的整数$a_1,a_2,\dots,a_n$，判定是否存在${1,2,\dots,n}$的子集$A$，使得$A$对应元素之和等于任意整数目标$T$。

归约的核心思路是通过符号转换和目标值偏移，将带负数的输入完全转换为符合标准子集和要求的全正输入，且两个问题的解一一对应，具体步骤如下：

步骤1：预处理原问题输入 #

• 先过滤掉原输入中的0：0不会影响子集和的结果，可选可不选，直接删除不影响判定结果。
• 计算两个统计值：
  • $N$：原输入中所有负数的绝对值之和
  • $M$：原输入中所有元素的绝对值之和
• 边界判断：如果目标$T < -M$或$T > M$，原问题直接返回False，因为所有可能的子集和的取值范围就是$[-M, M]$，超出范围不可能有解。如果$T+N <0$或$T+N > M$，同样直接返回False，因为构造出的标准子集和的目标值必然是非负且不超过$M$的。

步骤2：构造标准子集和输入 #

• 新的元素集合：将原输入的每个元素取绝对值，得到全为正整数的集合${|a_1|, |a_2|, \dots, |a_n|}$
• 新的目标值：$T' = T + N$，经过边界判断后$T'$必然是正整数，符合标准子集和的输入要求

步骤3：双向正确性证明 #

我们可以证明原问题有解当且仅当构造出的标准子集和问题有解：

正向（原问题有解→标准子集和有解） #

假设原问题存在子集$A$满足$\sum_{i\in A}a_i = T$，将等式变形：
$$\sum_{i\in A, a_i>0}a_i - \sum_{i\in A, a_i<0}|a_i| = T$$
两边同时加上所有负数的绝对值之和$N$：
$$\sum_{i\in A, a_i>0}|a_i| + \sum_{a_i<0, i\notin A}|a_i| = T + N = T'$$
上式左边的元素刚好构成新集合的一个子集，和为$T'$，因此标准子集和有解。

反向（标准子集和有解→原问题有解） #

假设构造的标准子集和存在子集$B$满足$\sum_{i\in B}|a_i| = T'$，我们构造原问题的子集$A$：

• 对于原输入中的正数$a_i$：$i\in A$当且仅当$i\in B$
• 对于原输入中的负数$a_i$：$i\in A$当且仅当$i\notin B$

计算$A$的和：
$$
\begin{align*}
\sum_{i\in A}a_i &= \sum_{i\in A,a_i>0}|a_i| - \sum_{i\in A,a_i<0}|a_i| \
&= \sum_{i\in B,a_i>0}|a_i| - \sum_{i\notin B,a_i<0}|a_i| \
&= (T' - \sum_{i\in B,a_i<0}|a_i|) - \sum_{i\notin B,a_i<0}|a_i| \
&= T + N - (\sum_{i\in B,a_i<0}|a_i| + \sum_{i\notin B,a_i<0}|a_i|) \
&= T + N - N = T
\end{align*}
$$
刚好符合原问题的目标要求，因此原问题有解。

归约复杂度说明 #

整个转换过程只需要遍历原输入一次完成统计和构造，时间复杂度为$O(n)$，属于多项式时间归约，因此可得：
SIGNED SUBSET SUM ≤ₚ SUBSET SUM

内容的提问来源于stack exchange，提问作者Iris Allevi