Skip to content

Instantly share code, notes, and snippets.

@dongr0510

dongr0510/target_sum.py

Created September 10, 2020 21:47
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save dongr0510/11a7561e5134d08d7157f0897f5980ee to your computer and use it in GitHub Desktop.
Save dongr0510/11a7561e5134d08d7157f0897f5980ee to your computer and use it in GitHub Desktop.
Download ZIP
Raw
target_sum.py
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