494. Target Sum - Unsolved
2024-10-15 04:46:21
https://leetcode.com/problems/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.
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:
- The length of the given array is positive and will not exceed 20.
- The sum of elements in the given array will not exceed 1000.
- Your output answer is guaranteed to be fitted in a 32-bit integer.
Sol 1:
http://blog.csdn.net/u014593748/article/details/70185208?utm_source=itdadao&utm_medium=referral
http://blog.csdn.net/Cloudox_/article/details/64905139?locationNum=1&fps=1
Java:
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int s) {
int sum = accumulate(nums.begin(), nums.end(), 0);
//(s + sum) & 1,判断s + sum的奇偶;(s + sum) >> 1,即(s + sum)/2
return sum < s || (s + sum) & 1 ? 0 : subsetSum(nums, (s + sum) >> 1); }
int subsetSum(vector<int>& nums, int s) {
int dp[s + 1] = { 0 };
dp[0] = 1;
for (int n : nums)
for (int i = s; i >= n; i--)
dp[i] += dp[i - n];
return dp[s];
}
};
My Python translation:
import collections
class Solution(object):
def findTargetSumWays(self, nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
""" # DP total = sum(nums)
if (total + S) % 2 != 0:
return 0 dp = [0] * (len(nums) + 1)
dp[0] = 1
for n in range(1, len(nums) + 1):
for i in range(S, n + 1, -1):
dp[i] += dp[i-n] return dp[S]
Sol 2:
https://discuss.leetcode.com/topic/76278/concise-python-dp-solution
def findTargetSumWays(self, nums, S):
self.dp = [defaultdict(int) for i in range(len(nums))]
return self.get_ways(nums, S, len(nums)-1) def get_ways(self, nums, S, i):
if i == -1:
return 1 if S == 0 else 0
if S not in self.dp[i]:
self.dp[i][S] = self.get_ways(nums, S + nums[i], i - 1) + self.get_ways(nums, S - nums[i], i - 1)
return self.dp[i][S]
最新文章
- OPEN CASCADE编译视频
- .Net语言 APP开发平台——Smobiler学习日志:如何快速实现地图定位时的地点微调功能
- WebDriver--操控浏览器
- JavaScript实现拖拽元素对齐到网格(每次移动固定距离)
- angularJS 2.0 开发的简单dome
- systemctl 命令的用法
- winform 承载 WCF 注意,可能不是工作在多线程模式下
- WPF学习之资源-Resources
- c#委托和事件(下) 分类: C# 2015-03-09 08:42 211人阅读 评论(0) 收藏
- Webview Android与js交互
- JavaScript高级内容:原型链、继承、执行上下文、作用域链、闭包
- JS应用实例3:定时弹出广告
- nowcoder172A 中位数 (二分答案)
- Navicat for MySQL安装工具及破解工具
- Mybatis六(SSM框架)
- linux 服务器删除大文件之后不释放存储空间的解决办法
- 重点:怎样正确的使用QThread类(注:包括推荐使用QThread线程的新方法QObject::moveToThread)
- 《C++ Primer Plus》14.4 类模板 学习笔记
- poj_1190 树状数组
- 洛谷P5292 [HNOI2019]校园旅行(二分图+最短路)