首页 > 代码库 > [Leetcode] DP -- Target Sum

[Leetcode] DP -- Target Sum

2024-10-11 23:47:39   216人阅读

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.

Solution:
 
1st use  DFS recursive,  like a binary tree;   Go to left (+1) or right (-1); then  when sum is S  go the upper next。
But it is TLE in python

 

 1     count = 0
 2     def findTargetSumWays(self, nums, S):
 3         def findTargetHelper(nums, index, S):
 4             if index == len(nums):
 5                 if S == 0:
 6                     self.count = self.count + 1
 7                 return
 8              
 9         
10             findTargetHelper(nums, index+1, S - nums[index])         #+1
11             findTargetHelper(nums, index+1, S + nums[index])         #-1
12         
13         findTargetHelper(nums, 0, S)
14 
15         return self.count

 

2.   DP
Refer to the other‘s idea that I didn‘t came up with .   
this problem could be transferred to subset sum problem (similar to knapback problem)
if there exist a solution,
P: positive number subset;     N: positive number subset
 then sum(P) - sum(N)  = S;               |P| + |N| = len(nums)
so  sum(P) + sum(N) + sum(P) - sum(N) =  S + sum(P) + sum(N)
         2*sum(P) = S + sum(nums)
            sum(P) = (S + sum(nums))/2
 the original problem  has been changed to a subset sum problem: :
Find a subset P of nums such that sum(P) = (target + sum(nums)) / 2
 
reference:
http://bgmeow.xyz/2017/01/29/LeetCode-494/
 
 1         def subsetSum(nums, target):
 2             dp = [0]*(target+1)
 3             dp[0] = 1
 4             for num in nums:
 5                 for j in range(target, num-1, -1):
 6                     dp[j] += dp[j-num]
 7                     #print ("dp: ", target, j, dp[j])
 8             return dp[target]
 9             
10         sumN = sum(nums)
11         
12         if sumN < S or (S+sumN) %2 != 0:
13             return 0
14         return subsetSum(nums, (S+sumN)>>1)

 

[Leetcode] DP -- Target Sum


联系
我们