题意就是先输入n,m,然后输入m个数,问在这m个数里有多少种任意相加起来等于n的方法,并且输出这些相加的数。
首先在进行dfs前我们可以把前面那些大于n的数省掉,比如说n是3,m个数为6,5,4,3,2,1,那么我们可以直接从第4个数开始进行dfs。然后在搜索到一种满足sum等于n的情况时, 我们需要有一个去重的操作(直接看代码吧)。
AC代码:
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int pre[10005];
int ans[10005];
int n,m;
int flag;
int num;
void Output(){
printf("%d",ans[0]);
for(int i=1;i<num;i++){
printf("+%d",ans[i]);
}
printf("\n");
}
void dfs(int x,int sum){
if(sum == n){
Output();
flag = 1;
return ;
}
if(sum > n)return ;
for(int i=x;i<m;i++){
ans[num++] = pre[i];
dfs(i + 1,sum + pre[i]);
num--;
while(i+1<m&&pre[i]==pre[i+1])i++; // 去重
}
}
int main()
{
while(scanf("%d%d",&n,&m)){
if(!n && !m) break;
for(int i=0;i<m;i++)scanf("%d",&pre[i]);
flag = 0;
num = 0;
int temp;
for(int i=0;i<m;i++){
if(pre[i] <= n){
temp = i;
break;
}
}
printf("Sums of %d:\n",n);
dfs(temp,0);
if(flag == 0)printf("NONE\n");
}
return 0;
}