PROBLEM :- LeetCode
Example >>5 1 1 1 1 1 3
output: 5.
//I just Memoized my recursive code but its giving Siggsev error . Recursive code was correct .
Please run on online compiler not on leetcode compiler as I have not used vectors as specified in question .I will change it later .
#include <iostream>
using namespace std;
#include<bits/stdc++.h>
int dp[10001][10001];
int rec(int *arr ,int sum,int n)
{
if(n<0 || (sum!=0 && n==0))
{
return 0 ;
}
if(n==0 && sum==0)
{
return 1;
}
if(dp[sum][n]!= -1)
{
return dp[sum][n];
}
dp[sum][n]= rec(arr,sum-arr[n-1],n-1) + rec(arr,sum+arr[n-1],n-1);
return rec(arr,sum-arr[n-1],n-1) + rec(arr,sum+arr[n-1],n-1);
}
int main()
{
int n,sum;
for(int i=0;i<10001;i++)
{
for(int j=0;j<10001;j++)
{
dp[i][j]=-1;
}
}
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
cin>>sum;
cout<<rec(arr , sum, n);
}
What if Sum becomes negative? You’ll need two dps, one to keep track of positive sum and one to keep track of negative sum.
Also, the equestrian doesn’t really expect memorisation. n < 21 so an exponential solution is fine. It’s nice that you’re trying out top-down dp with it though.
And also, I’d advice you to use C++ vectors, instead of C style arrays even when you code locally or for any other competitions. Some exceptions such as out of bounds access can be captured using some compile flags for C++ containers, but those don’t work on C style array.
1 Like
What if I add this to my code
if((sum<0 && n<=0))
{
return 0 ;
}
,It still gives error, sum can be negative while we do the operations(provide n is not 0 yet) and after addition it can become positive until n!=0
I think you are talking about this??
if((sum<0 && n<=0))
{
return 0 ;
}
,It still gives error, sum can be negative while we do the operations(provide n is not 0 yet) and after addition it can become positive until n!=0
My mistake, it wiil not be correct as if sum is negative then also it can give answer after adding some values to it
It should be (sum < 0 || n <= 0). If you use and, then it will flow down even if sum < 0, and that leads to segmentation fault.
(But I’m pretty sure you’ll get WA if you return 0 if the sum < 0)
2 Likes