Leetcode 494 Target Sum

发表于 |

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例 1:
输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解释:
-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
一共有5种方法让最终目标和为3。

注意:

  1. 数组的长度不会超过20，并且数组中的值全为正数。
  2. 初始的数组的和不会超过1000。
  3. 保证返回的最终结果为32位整数。

分析：

  1. 这道题可以单纯的用暴力法解决，也就是对每个元素分别进行一次正负的累加，复杂度为2^n，因为n不超过20，故也就100w左右，但是在leetcode上同样的解法c++和java可以通过，python是无法通过的
  2. 这里介绍discuss里一位大神提出来的超帅的数学解法，这道题中我们加正负号无非是将nums分为两个子集p,n，p中元素全部加正号，n中元素全部加负号，使得sum(p) - sum(n) = S，而本身又有sum(p) + sum(n) = sum(nums)，故两式相加化简得sum(p) = (sum(nums)+S) / 2
  3. 那么这个式子直接给出了一个信息，也就是如果能找到p，则必有sum(nums)+S % 2 == 0这个条件，这个条件可以帮我们快速判断是否有解。
  4. 那么此时题目就变成给定一个数组nums，求有多少组不同的p，使得sum(p) = target，直接dp可解

思路：

  1. 建立dp，dp[i] = j代表数组nums中有j组子集的和为i，初始dp[0] = 1
  2. 如nums = [1,1,1,1,1]，按照如下步骤分析
    1. 对nums[0]分析，则得dp[1] = 1(因为dp[0] = 1)
    2. 对nums[1]分析，则得dp[1] = 2,dp[2] = 1(因为dp[0] = 1,dp[1] = 1)
    3. 对nums[2]分析，则得dp[1] = 3,dp[2] = 2,d[3] = 1,依次类推
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def findTargetSumWays(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        if sum(nums) < S: return 0
        if (sum(nums) + S) & 1: return 0

        target = (sum(nums) + S) / 2
        dp = [0] * (target+1)
        dp[0] = 1

        for i in range(len(nums)):
            for val in range(target, nums[i]-1, -1):
                if dp[val-nums[i]]:
                    dp[val] += dp[val-nums[i]]
        return dp[-1]

O(n*sum(nums)) time, O(sum(nums)) space
139 / 139 test cases passed.
diffculty: medium
Runtime: 91 ms,beats 95.24%