Help me out in this

#1



help me out

#2

@amanyadav211 are u there ?

#3

yeah , pls wait ,checking ur code

#4

pls check ur updated code here->


class Solution {
public:
    int fs;// target sum
int n;
int dp[201][20001];

// recursive with memoization is as fast as top down approach//
int subset(vector<int> &ar,int i,int sum)//pass ar by refrence to avoid copying time 
{
	if(sum==fs)
	{
		return 1;
	}
	if(i>=n || sum>fs)
	{
		return 0;
	}
	if(dp[i][sum]!=-1)
	{
		return dp[i][sum];
	}
	// if the current element is graeter than 
	if(ar[i]>fs)
	{
		return subset(ar,i+1,sum);
	}
	// either include or exclude the current element//
	int ans1=subset(ar,i+1,sum+ar[i]);
	int ans2=subset(ar,i+1,sum);
	return dp[i][sum]=ans1||ans2;
}

    bool canPartition(vector<int>& nums) {
         n=nums.size();
        int sum=0;
    
        for(int i=0;i<n;i++)
        {
            sum=sum+nums[i];
        }
    for(int i=0;i<201;i++)
    {
	  for(int j=0;j<20000;j++)
	  {
		dp[i][j]=-1;
	    }
    }
        if(sum%2!=0)
        { 
            return false;
        }
        fs=sum/2;
        if(subset(nums,0,0))
        {
            return true;
        }
        else
        {
            return false;
        }
        
    }
};

read difference b/w pass by value and pass by refrence (if the change dont make sense to u)

#5

@aman212yadav ya i know bro i am making the copy of nums that why it is taking tle?
i have to ask one thing there is any differnece in time compexity of recurive with memoization and top down approach?

#6

yeah the ar array vector get copied to new vector for evry function call thats the reason for tle…

recursion + memoisation table(dp array) = top down dp only
u mean top down vs bottom up?.
no time complexity wise they are almost same .

time complexity in case of top down -> num of distinct states * transition time.

for bottom up its easy just count loops

#7

@aman212yadav okay bro thank u

#8

@aman212yadav can you suggest good sets of question for dp for practice ?

#9
  1. -> atcoder (26 problems) covers almost all dp variations
  2. -> cses dp problemset
  3. -> leet code has around 200 problems on dp u can try that as well.

interview bit has also around 50 problems try that as well.
gfg for standard dp questions.

#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.