You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols +
and -
. For each integer, you should choose one from +
and -
as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S.
Example 1:
Input: nums is [1, 1, 1, 1, 1], S is 3. Output: 5 Explanation: -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 There are 5 ways to assign symbols to make the sum of nums be target 3.
sum(P)-sum(n)=target; sum(P)-sum(n)+sum(P)+sum(n)=target+sum(P)+sum(n); 2*sum(P)=target+sum(nums); sum(P)=(target+sum(nums))/2; 最后转换为求sum(P),即数组中有几个组合加起来等于sum(P) dp[i]的意思是:元素和为i的话有几种情况, 当前元素为4时,则dp[i] = dp[i] + dp[i-4]; dp[9] = dp[9] + dp[9-4]; dp[8] = dp[8] + dp[8-4]; dp[7] = dp[7] + dp[7-4]; dp[6] = dp[6] + dp[6-4]; dp[5] = dp[5] + dp[5-4]; dp[4] = dp[4] + dp[4-4];
public static int findTargetSumWays(int[] nums, int target) {标签:target,nums,int,Sum,symbols,494,sum,dp,Target From: https://www.cnblogs.com/MarkLeeBYR/p/17223865.html
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}
if (target > sum || (sum + target) % 2 == 1)
return 0;
return subsetSum(nums, (sum + target) / 2);
}
private static int subsetSum(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1; //C(0,0)=1
for (int i = 0; i < nums.length; i++) {
for (int j = target; j >= 0; j--) {
if (j >= nums[i])
dp[j] += dp[j - nums[i]];
}
}
return dp[target];
}