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:
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]
原文：http://www.cnblogs.com/prmlab/p/7158102.html