494.Target Sum

标签：target nums int Sum symbols 494 sum dp Target

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) {
    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];
}

标签：target,nums,int,Sum,symbols,494,sum,dp,Target
From： https://www.cnblogs.com/MarkLeeBYR/p/17223865.html