Skip to content

Instantly share code, notes, and snippets.

@dongr0510
Created September 10, 2020 21:47
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Embed
What would you like to do?
def findTargetSumWays(nums: List[int], S: int) -> int:
totalSum = sum(nums)
if totalSum < S or (S + totalSum) % 2 == 1:
return 0
n = len(nums)
s_total = int((S+totalSum)/2)
dp = [0 for _ in range(s_total+1)]
dp[0] = 1
for num in nums:
for j in range(s_total,num-1,-1):dp[j] += dp[j - num]
return dp[-1]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment