Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
subset sum=k(dp)
#include<bits/stdc++.h> using namespace std; int dp[10][10]; bool check(vector<int>v,int n,int sum) { if(dp[n][sum]!=-1) { return dp[n][sum]; } else if(sum==0 && n==0) { return dp[n][sum]=1; } else if(sum!=0 && n==0) { return dp[n][sum]= 0; } else if(sum==0 && n!=0) { return dp[n][sum]=1; } else if(v[n-1]>sum) { return dp[n][sum]=check(v,n-1,sum); } else { return dp[n][sum]=(check(v,n-1,sum) || check(v,n-1,sum-v[n-1])); } } int main() { memset(dp,-1,sizeof(dp)); int n; cin>>n; int sum; cin>>sum; vector<int>v; for(int i=0;i<n;i++) { int g; cin>>g; v.push_back(g); } int c=check(v,n,sum); if(c) { cout<<"Y"<<endl; } else { cout<<"N"<<endl; } }
run
|
edit
|
history
|
help
0
Rotate array
Stock buy/sell, maximum subarray problem
MACRO
Display all prime numbers upto N without sieve
FindMissingLagrange
Chinu
merge-sort
good triplet
PalindromePair-s1
uuuu