Xenomorphing_19's blog

By Xenomorphing_19, 3 years ago, In English

I've been trying a Problem: Target Sum in Dynamic Programming. I tried solving it by two methods: 1. recursion with memorization 2. Tabular DP In the second method, I'm receiving a WA verdict for the cases having all the elements equal. I've checked multiple sources if there is an error in my code but the codes which I found on those sites are also giving wrong answers[identical to my code]. I am unable to get my code work correctly. Here are both the codes I've written. Thanks in Advance.

Tabular DP

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0;
        for(auto it:nums) sum+=it;
        int n=nums.size();
        sum+=target;
        if(sum%2!=0) return 0;
        sum/=2;
        int dp[n+1][sum+1];
        sort(nums.begin(),nums.end());
        for(int i=0;i<=sum;i++) dp[0][i]=0;
        for(int i=0;i<=n;i++) dp[i][0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=sum;j++)
            {
                if(nums[i-1]<=j) dp[i][j] = dp[i-1][j-nums[i-1]] + dp[i-1][j];
                else dp[i][j] = dp[i-1][j];
            }
        }
        return dp[n][sum];
    }
};

Recursion with Memoization

class Solution {
public:
    map <pair<int,int>,int> mp;
    int solve(vector <int> &A,int target, int ind, int sum)
    {
        if(ind==A.size())
        {
            if(sum==target) return 1;
            return 0;
        }
        if(mp.find({ind,sum})!=mp.end()) return mp[{ind,sum}];
        int a=solve(A,target,ind+1,sum+A[ind]);
        int b=solve(A,target,ind+1,sum-A[ind]);
        return mp[{ind,sum}] = (a+b);
    }
    int findTargetSumWays(vector<int>& nums, int target) {
        mp.clear();
        return solve(nums,target,0,0);
    }
};
  • Vote: I like it
  • +7
  • Vote: I do not like it