[Leetcode] 494. Target Sum | 目标和

yPhantom 2020年02月03日 19次浏览

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.

Note:

  1. The length of the given array is positive and will not exceed 20.
  2. The sum of elements in the given array will not exceed 1000.
  3. Your output answer is guaranteed to be fitted in a 32-bit integer.

这道题给出一个数组,数组中的每个数字都可以用+号或者-号进行连接,最后求得一个和sum,问sum为指定值一共有多少种方式。

这道题的技巧在于它实质上是求在数组中找一个子集,其和为指定值,一共有多少种组合情况。那么,究竟是如何转化的呢?

看到题目需要仔细分析,它能转换成哪些形式,其实质是考察什么

我们假设P代表被+号修饰的子集,N代表被-号修饰的子集,那么有:

P - N = target
P + N = sum

P - N + P + N = target + sum
p = (target + sum) / 2

因此,我们是在求数组中和为(target + sum) / 2的子集有多少种组合情况。这让我想到以前做过的题416. Partition Equal Subset Sum,其实质就是一个背包问题。直接附上代码吧:

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int n : nums)
            sum += n;
        return sum < S || (S + sum) % 2 > 0 ? 0 : subsetSum(nums, (S + sum) >>> 1); 
    }   

    public int subsetSum(int[] nums, int s) {
        int[] dp = new int[s + 1]; 
        dp[0] = 1;
        for (int n : nums)
            for (int i = s; i >= n; i--)
                dp[i] += dp[i - n]; 
        return dp[s];
    }
}

subsetSum函数具体可以去看416题的解法

参考资料

Java (15 ms) C++ (3 ms) O(ns) iterative DP solution using subset sum with explanation