#include
using namespace std;
#define MOD 1000000007
int output[1000001][101];
int moneyChange(int change, int* arr, int size){
if(change == 0){
return 1;
}
if(change < 0){
return 0;
}
if(size == 0 ){
return 0;
}
if(output[change][size]>-1){
return output[change][size];
}
int first = moneyChange(change - arr[0] , arr, size);
int second = moneyChange(change, arr+1, size-1);
output[change][size] = (int)(((long long)first + second)%MOD);
return output[change][size];
}
int main() {
// cout<<“Hello World!”;
int t;
cin>>t;
while(t–){
int n;
cin>>n;
int* arr = new int[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
int change;
cin>>change;
for(int i=0; i<1000001; i++){
for(int j=0; j<101; j++){
output[i][j] = -1;
}
}
cout<<moneyChange(change,arr,n)<<endl;
delete [] arr;
}
}
problem–> two test cases got passed while 6 are WA.
Question-> https://hack.codingblocks.com/contests/c/452/1026