10-9 LeetCode 494. Target Sum

Target Sum

Description

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.

给你一个列表和一个目标整数 S，列表元素都是非负整数，你有+和-两个符号，对列表里的每一个整数，你需要选择其中一个符号作为他的符号。

找出一共有多少种方法来分配符号是列表元素的和等于目标整数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 lengThe 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.

Solution 1():

几乎所有题目都可以使用蛮力法，我用递归和循环两种方式去使用蛮力法，结果都没有解决，都超时了。。。。。

超时代码如下：

`class Solution(object):

def findTargetSumWays(self, nums, S):
    """
    :type nums: List[int]
    :type S: int
    :rtype: int
    """
    if not nums:
        return 0
    front = [nums[0], -nums[0]]
    for i in range(len(nums))[1:]:
        length = len(front)
        for j in range(length):
            front.append(front[j]-nums[i])
            front[j] = front[j] + nums[i]
    count = 0
    for num in front:
        if num == S:
            count += 1
    return count`

然后就想着如何优化这种方法，于是用字典这种数据结构代替列表，这样就可以在循环的过程中直接求出方法数，省去最后一个for sum in front循环，毕竟这个数据非常大。

改进代码如下：

`class Solution(object):

def findTargetSumWays(self, nums, S):
    """
    :type nums: List[int]
    :type S: int
    :rtype: int
    """
    if not nums:
        return 0
    dic = {nums[0]: 1, -nums[0]: 1} if nums[0] != 0 else {0 : 2}
    for i in range(1, len(nums)):
        temp_dic = {}
        for d in dic:
            temp_dic[d + nums[i]] = temp_dic.get(d + nums[i], 0) + dic.get(d, 0)
            temp_dic[d - nums[i]] = temp_dic.get(d - nums[i], 0) + dic.get(d, 0)
        dic = temp_dic
    return dic.get(S, 0)`

Solution 2

这是参考了大神的做法。

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

先根据数学的关系，将问题优化。

集合P包括所有符号为正的整数，集合N包括所有符号为负的整数。可以得出如下关系：

sum(P) - sum(N) = target

sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)

2*sum(P) = target + sum(nums)

于是这题目就变成求有多少中子集合的和为 (target + sum(nums))/2。 具体过程参考链接。

感想

这是第一次写，写的不是很好。主要是时间紧，对问题没有那么多时间分析，也是一个摸索的阶段，在摸索如何写的精简和易懂，毕竟大家都很忙。谢谢阅读！