如何将含正负整数的数组转换为正整数数组并适配子集和问题？

问题根源 #

你提到的转换方法（取最小元素绝对值+1作为偏移量，将数组转为正整数）本身没问题，但直接用转换后的数组做子集和时，目标和需要结合子集元素个数才能准确对应原问题的目标和——只简单叠加偏移量×元素数会出现假阳性，因为不同大小的子集可能算出相同的转换后和。

可靠解法：带元素计数的动态规划 #

实现步骤 #

1. 计算偏移量：找到原数组的最小元素min_val，偏移量offset = abs(min_val) + 1，将原数组每个元素转为x = num + offset（确保所有元素为正整数）。
2. 定义DP状态：用二维布尔数组dp[s][k]表示「是否存在包含k个元素的子集，其转换后的和为s」。也可以用字典嵌套字典优化空间：外层键为转换后的和s，内层键为元素个数k，值为布尔值（仅存储可达状态）。
3. 初始化状态：dp[0][0] = True（空子集，和为0，元素数为0）。
4. 遍历更新状态：
   对每个转换后的元素x，逆序遍历已记录的和s，再遍历对应的元素个数k：
   • 如果dp[s][k]为True，则标记dp[s + x][k + 1] = True。
5. 验证目标和：遍历所有可能的子集元素个数k，检查是否存在dp[target + k * offset][k]为True——如果存在，说明原数组中存在和为target的子集。

这种方法通过同时追踪「转换后的和」与「子集元素个数」，彻底避免了假阳性问题，时间复杂度和常规子集和DP一致（O(n * S)，其中S为转换后数组的最大可能和）。

更优思路：直接处理正负数组 #

其实无需强制转成正整数数组，可直接针对含正负的数组调整动态规划逻辑：

1. 计算负数总和：统计原数组所有负数的绝对值之和neg_total。
2. 偏移所有元素：将原数组每个元素加上neg_total，得到全非负数组（负数转为abs(num)，正数变为num + neg_total）。
3. 调整目标和：原目标和target调整为target + neg_total。
4. 常规子集和DP：用0-1背包DP检查调整后的目标和是否可达——若可达，则原数组存在对应子集。

这个思路本质是通过一次偏移将所有元素转为非负，同时同步调整目标和，无需额外追踪元素个数，实现更简洁。

内容的提问来源于stack exchange，提问作者Talon Van Vuuren