题目大意:给你一个结果和n个数,你要找到这n个数能使得和为结果的序列输出出来,并且序列不重复
解题思路:这是一道DFS+路径的题,因为题目的序列为不上升,你就只需要判断相邻的会不会重复就行,即每次用一个变量存序列中len位置的上一个值,如果该位置往下找的数会和上一次的数一样就筛掉。
(因为一开始没注意是不上升序列 还在想如果遇到像10 14 5 5 1 1 1 1 1 5 5 1 1 1 1 1这种情况怎么办,其实这种情况目前能想到的情况就是把能够成为目前答案的序列存入一张表中,每次找到一段合法序列就去查表)
AC代码如下:
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n,s,answer[200],map[200],flag;
void dfs(int x,int sum,int len)
{
if(sum==s && len)
{
flag=1;
for(int i=0;i<len;i++)
if(i<len-1)
printf("%d+",answer[i]);
else
printf("%d\n",answer[i]);
return ;
}
int i,k=-1;
for(i=x;i<n;i++)
if(sum+map[i]<=s && k!=map[i])
{
k=answer[len]=map[i];
dfs(i+1,sum+answer[len],len+1);
}
return ;
}
int main()
{
int i,t;
while(~scanf("%d%d",&s,&n) && s+n)
{
t=flag=0;
for(i=0;i<n;i++)
{
scanf("%d",&map[i]);
t+=map[i];
}
printf("Sums of %d:\n",s);
if(t<s)
{
puts("NONE");
continue;
}
dfs(0,0,0);
if(!flag)
puts("NONE");
}
return 0;
}