#### Recursive solution of ordered Coin Combinations II (CSES)

Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ordered ways you can produce a money sum x using the available coins.

For example, if the coins are {2,3,5} and the desired sum is 9, there are 3 ways:

``````2+2+5
3+3+3
2+2+2+3
``````

I am trying to write recursive solution for this.
I came up with this code.

``````#include<iostream>
#include<vector>
using namespace std;
#define M 1000000007

vector<int>arr;
vector<vector<int>>dp;

int solve(int i,int target){
if(i>=(int)arr.size()) return 0;
if(target<0) return 0;
if(target==0) return 1;
if(dp[i][target]!=-1) return dp[i][target];
return dp[i][target]=(solve(i,target-arr[i])%M+solve(i+1,target)%M)%M;
}

int main(){
int n,target;
cin>>n>>target;
arr.resize(n);
dp.resize(n+1,vector<int>(target+1,-1));
for(int i=0;i<n;++i){
cin>>arr[i];
}
cout<<solve(0,target);
}
``````

but this code is giving time-limit-exceeded. How can this code be written in a recursive manner so that it gets accepted? Here is non-recursive approach but I want to know how to write a recursive version of this.

Source: Windows Questions C++