本文共 1252 字，大约阅读时间需要 4 分钟。

题目：组成目标数有多少种方法？

思路：

举例说明: nums = {1,2,3,4,5}, target=3, 一种可行的方案是+1-2+3-4+5 = 3

该方案中数组元素可以分为两组，一组是数字符号为正(P={1,3,5})，另一组数字符号为负(N={2,4}) 因此: sum(1,3,5) - sum(2,4) = target          sum(1,3,5) - sum(2,4) + sum(1,3,5) + sum(2,4) = target + sum(1,3,5) + sum(2,4)          2sum(1,3,5) = target + sum(1,3,5) + sum(2,4)          2sum(P) = target + sum(nums)          sum(P) = (target + sum(nums)) / 2 由于target和sum(nums)是固定值，因此原始问题转化为求解nums中子集的和等于sum(P)的方案个数问题。

如果 sum(nums) 小于 S或者 （sum(nums) + S） % 2 ！=0 表示不能组成目标数，返回0。

应用dp解决子集合问题：

dp[y]+=dp[y-num]，表示组成数值y的方案数等于原来组成数值y的方案数 + 组成数值y-num的方案数

例如

dp[8] = dp[8] + dp[8-1] (假设数组为: 1 2 3 4 5) dp[8] = dp[8] + dp[8-2] dp[8] = dp[8] + dp[8-3] dp[8] = dp[8] + dp[8-4] dp[8] = dp[8] + dp[8-5]

dp代码

for(int num : nums)     for(int y=target;y>=num;y--)        dp[y]+=dp[y-num];

完整代码：

class Solution {public:    int findTargetSumWays(vector
   
    & nums, int S) {        int sum = 0;        for(int num : nums) sum+=num;        if (sum < S || (sum + S) % 2 != 0)           return 0;        int target = (sum+S)>>1;        int dp[target+1];        memset(dp,0,sizeof(dp));        dp[0] = 1;        for(int num : nums)             for(int y=target;y>=num;y--)                dp[y]+=dp[y-num];     return dp[target];       }};
   

转载地址：http://unrai.baihongyu.com/