In “Subset Problem”
I have written the following code, it gives WA. Can someone please help out?
#include<iostream>
#include<string.h>
using namespace std;
int dp[1002][1002];
bool f(int arr[], int n, int sum){
if(n==0 && sum!=0) return false;
else if(sum==0) return true;
else if(arr[n-1]>sum) return f(arr,n-1,sum);
else{
if(dp[n][sum]!=-1) return dp[n][sum];
else{
if(f(arr, n-1, sum-arr[n-1]) || f(arr, n-1, sum)) dp[n][sum]=1;
else dp[n][sum]=0;
return dp[n][sum];
}
}
}
int main(){
int t;
cin>>t;
while(t--){
int n,sum;
cin>>n>>sum;
memset(dp, -1, sizeof(dp[0][0]) * n * sum);
int arr[n];
for(int i=0;i<n;i++) cin>>arr[i];
if(f(arr, n, sum)) cout<<1<<endl;
else cout<<0<<endl;
}
}