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
class Solution:
def findTargetSumWays(self, nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
"""
n = len(nums)
if n == 0:
return 0
ss = sum(nums)
if( S>ss or S<-ss) :
return 0
ssum = ss*2
dp = [[0] * (ssum+1) for _ in range(n + 1)]
dp[0][ss] = 1
for i in range(1, n + 1):
for j in range(0, ssum+1):
if j - nums[i - 1]>=0:
dp[i][j] = dp[i - 1][j - nums[i - 1]]
if j + nums[i - 1] <= ssum:
dp[i][j] += dp[i - 1][j + nums[i - 1]]
return dp[n][S+ss]
dfs with memo
记住判断map的key是否存在 是key in dict,不是dict[key]或者Get(key)
class Solution:
def findTargetSumWays(self, nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
"""
n = len(nums)
d = {}
return self.dfs(nums,0,S,0,d)
def dfs(self,nums,sum,S,pos,d):
if (pos, sum) in d:
return d.get((pos,sum))
if pos == len(nums):
return 1 if S ==sum else 0
l = self.dfs(nums,sum-nums[pos],S,pos+1,d)
r = self.dfs(nums,sum+nums[pos],S,pos+1,d)
cur = l+r
d[(pos,sum)] = cur
return cur
class Solution(object):
def findTargetSumWays(self, nums, S):
s = sum(nums)
N = s+S
if N%2 or S>s: return 0
N = N//2
dp = [0 for _ in xrange(N+1)]
dp[0] = 1
for num in nums:
for i in xrange(N, num-1, -1):
dp[i] += dp[i-num]
return dp[-1]
#01 knapsack
# sum(p) - sum(q) = S
# sum(p) + sum(q) = sum(all)
# sum(p) = (sum(all) + S)/2
网上做法2
#include <vector>
#include <numeric>
using namespace std;
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (S > sum || S < -sum || S + sum < 0 || (S + sum) % 2 == 1) {
return 0;
}
int target = (S + sum) / 2;
int n = nums.size();
vector<vector<int>> dp(n + 1, vector<int>(target + 1, 0));
dp[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= target; ++j) {
dp[i][j] = dp[i - 1][j];
if (nums[i - 1] <= j) {
dp[i][j] += dp[i - 1][j - nums[i - 1]];
}
}
}
return dp[n][target];
}
};
#if DEBUG
int main(int argc, char** argv) {
return 0;
}
#endif