0494. Target Sum ================ 题目信息 -------- :题号: 0494 :难度: Medium :主题: 非负整数、正负号分配、表达式结果、方案计数 :原题: `LeetCode 0494 `_ :重点: 每个数组元素前必须放 ``+`` 或 ``-``、保持原顺序、不同符号选择分别计数、零的两种符号也不同 题目重述 -------- 给定非负整数数组 ``nums`` 和整数 ``target``。必须在每个元素前放置一个 ``+`` 或 ``-``,按原数组顺序组成算术表达式。返回表达式计算结果恰好等于 ``target`` 的不同符号分配方案数量。 ``nums.length`` 位于 ``[1, 20]``,每个元素位于 ``[0, 1000]``,全部元素之和不超过 ``1000``,``target`` 位于 ``[-1000, 1000]``。每个位置都必须选择一个符号;即使元素值为 0,``+0`` 和 ``-0`` 也是两种不同方案。 自建示例 -------- 两种不同位置的负号选择: .. code-block:: text 输入:nums = [1,2,1],target = 2 输出:2 解释:+1+2-1 和 -1+2+1 都等于 2,因此有两种方案。 零产生两个符号方案: .. code-block:: text 输入:nums = [0,1],target = 1 输出:2 解释:+0+1 与 -0+1 的数值相同,但第一个位置选择的符号不同,应分别计数。 把正号集合转换成子集和计数 -------------------------- 设所有元素总和为 ``S``,被放正号的元素和为 ``P``,被放负号的元素和为 ``M``。则 ``P-M=target``、``P+M=S``,所以必须有 ``P=(S+target)/2``。若 ``|target| > S`` 或 ``S+target`` 为奇数,答案直接为 0。 随后变成 0/1 背包:``dp[j]`` 表示处理过的元素中和为 ``j`` 的符号分配数。每个元素只处理一次,容量从目标和向下更新;值为 0 时 ``dp[j]`` 会自我相加,正好保留 ``+0`` 与 ``-0`` 的两种不同选择。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int findTargetSumWays(std::vector& nums, int target) { int total = std::accumulate(nums.begin(), nums.end(), 0); if (std::abs(target) > total || (total + target) % 2 != 0) { return 0; } int positiveSum = (total + target) / 2; std::vector dp(positiveSum + 1, 0); dp[0] = 1; for (int value : nums) { for (int sum = positiveSum; sum >= value; --sum) { dp[sum] += dp[sum - value]; } } return dp[positiveSum]; } }; 代码分析 -------- 正号子集一旦确定,负号集合也随之确定,子集和计数与符号方案一一对应;倒序更新避免同一元素被重复放入,零值在 ``sum`` 不变时仍会使方案数翻倍。时间复杂度为 ``O(nS)``,空间复杂度为 ``O(S)``。