首页 > 代码库 > 494. Target Sum - Unsolved
494. Target Sum - Unsolved
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]
494. Target Sum - Unsolved
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。