Target Sum — DP Count Ways
Sanjeev SharmaAdvertisement
Problem
Assign + or - to each element. Count ways to reach target.
Approach — Math Reduction + Knapsack
Let P = subset of positives, N = negatives. P - N = target, P + N = total. So P = (total + target) / 2. Count subsets summing to P.
Time: O(n * P) | Space: O(P)
Solutions
Python
class Solution:
def findTargetSumWays(self, nums: list[int], target: int) -> int:
total=sum(nums)
if (total+target)%2 or abs(target)>total: return 0
P=(total+target)//2
dp=[0]*(P+1); dp[0]=1
for n in nums:
for j in range(P,n-1,-1): dp[j]+=dp[j-n]
return dp[P]
C++
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target){
int total=accumulate(nums.begin(),nums.end(),0);
if((total+target)%2||abs(target)>total) return 0;
int P=(total+target)/2; vector<int> dp(P+1,0); dp[0]=1;
for(int n:nums) for(int j=P;j>=n;j--) dp[j]+=dp[j-n];
return dp[P];
}
};
Complexity
- Time: O(n * sum) | Space: O(sum)
Advertisement
