前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode-Medium 494. Target Sum

Leetcode-Medium 494. Target Sum

作者头像
致Great
发布2019-03-15 16:21:16
7480
发布2019-03-15 16:21:16
举报
文章被收录于专栏:程序生活

题目描述

给定一个非负整数序列,a1, a2, …, an,和一个目标值 S。现在你有两种符号 + 和 -。对于每个整数,你可以选择为其选择一个符号。找到有多少种添加符号的方式使其目标值等于 S。

实例:

代码语言:javascript
复制
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.

思路

  • 递归 Java可以通过,Python不可以
代码语言:javascript
复制
public class Solution {
    int count = 0;
    public int findTargetSumWays(int[] nums, int S) {
        calculate(nums, 0, 0, S);
        return count;
    }
    public void calculate(int[] nums, int i, int sum, int S) {
        if (i == nums.length) {
            if (sum == S)
                count++;
        } else {
            calculate(nums, i + 1, sum + nums[i], S);
            calculate(nums, i + 1, sum - nums[i], S);
        }
    }
}
  • 动态规划 在讨论区看到的数据技巧:
代码语言:javascript
复制
1、该问题求解数组中数字只和等于目标值的方案个数,每个数字的符号可以为正或负(减整数等于加负数)。

2、该问题和矩阵链乘很相似,是典型的动态规划问题

3、举例说明: nums = {1,2,3,4,5}, target=3, 一种可行的方案是+1-2+3-4+5 = 3

     该方案中数组元素可以分为两组,一组是数字符号为正(P={1,3,5}),另一组数字符号为负(N={2,4})

     因此: sum(1,3,5) - sum(2,4) = target

              sum(1,3,5) - sum(2,4) + sum(1,3,5) + sum(2,4) = target + sum(1,3,5) + sum(2,4)

              2sum(1,3,5) = target + sum(1,3,5) + sum(2,4)

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

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

     由于target和sum(nums)是固定值,因此原始问题转化为求解nums中子集的和等于sum(P)的方案个数问题

https://blog.csdn.net/hit0803107/article/details/54894227

代码实现

代码语言:javascript
复制
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]

https://buptwc.com/2018/07/03/Leetcode-494-Target-Sum/

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019.03.04 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 思路
  • 代码实现
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档