思路：dp,有点类似背包，不过不需要求最大价值，只要求方案数就可以了。

状态：dp[i]表示和为i的方案数

初始状态：dp[0]=1

状态转移：dp[i]=∑dp[i-a[k]] (1<=k<=n)

用一个pre[]数组来记录路径

代码：

#include
     
      using namespace std;#define ll long long#define pb push_back#define mem(a,b) memset(a,b,sizeof(a))const int N=1e5+5;int dp[N];int pre[N];int a[N];bool vis[N];vector
      
       ans;int main(){    ios::sync_with_stdio(false);    cin.tie(0);    int m,n;    cin>>m;    cin>>n;    for(int i=1;i<=n;i++)cin>>a[i];    if(m>1e5){        cout<<0<
       
        =a[i];j--){            if(dp[j-a[i]]){                dp[j]+=dp[j-a[i]];                if(pre[j]==-1)pre[j]=i;            }        }    }    if(dp[m]==0)cout<<0<