please help why TLE,
is there any logical error or something else??
my code
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
typedef long long ll;
ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);}
ll inf = 1000000000;
int dp[10000000];
int mod = 1000000000+7;
int permtation(int sum, vector<int> &coin, int n){
if(sum==0) return 1;
if(sum<0) return 0;
if(dp[sum]!=-1) return dp[sum];
int count = 0;
for(int i=0;i<n;i++){
if(sum-coin[i]<0) break;
count+=(permtation(sum-coin[i],coin,n));
count%=mod;
}
return dp[sum] = count;
}
void solve(){
int sum;
int n;
cin>>n>>sum;
vector<int> coin(n);
for(int i=0;i<n;i++){
cin>>coin[i];
}
sort(coin.begin(),coin.end());
memset(dp,-1,sizeof(dp));
int ans = permtation(sum,coin,n);
cout << ans;
}
int main(){
ios_base::sync_with_stdio(0) ;
cin.tie(0) ; cout.tie(0) ;
cout.precision(20);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int T=1; //cin>>T;
while(T--){
solve();
if(T)cout << endl;
}
return 0;
}
TLE on this input
100 1000000
27 69 68 13 1 63 28 44 45 67 57 11 8 85 42 20 32 77 39 52 70 24 4 79 7 15 54 88 51 73 89 66 48 56 47 18 2 30 21 49 74 9 99 83 55 95 62 90 22 31 71 98 43 75 25 16 12 64 61 38 40 26 3 96 41 86 5 14 91 33 78 50 23 84 94 36 46 97 53 81 65 34 93 59 6 35 72 10 82 60 19 92 29 87 76 100 80 17 58 37
