494. 目标和
https://leetcode-cn.com/problems/target-sum
题目描述
思路 1: DP
简单理解一下题目就是,我们要从数组中选出一个正数集,然后剩下的数字自动变成了一个负数集,这两个集合的和要刚好等于目标数 S。
换句话说,我们要从原数组中选出一个子集,满足元素的和为 target(这个 target 不是原题中的 S),只要确定这个 target,剩下就是 0-1 背包问题的套路了。
已知:
正数集 + 负数集 = S
正数集 - 负数集 = sum
sum 是原数组的和。
可得:
正数集 = (S + sum) / 2
所以 (S + sum) / 2
就是我们要找的 target。
复杂度
时间复杂度:$O(len*(sum+S)/2)$,len 是数组长度,sum 是数组元素和,S 是目标数。
空间复杂度:$O((sum+S)/2)$。
代码
JavaScript Code
思路 2: DFS
DFS 枚举所有排列组合,计算组合的和,如果满足和等于 S 则结果++。
复杂度
时间复杂度:$O(2^n)$,n 是数组长度。
空间复杂度:$O(logn)$。
代码
JavaScript Code
Originally posted by @suukii in https://github.com/leetcode-pp/91alg-1/issues/109#issuecomment-678378367
Last updated
Was this helpful?