1711.cpp

自己的ac代码 在acm.zju.edu.cn 上的题目

#include<stdio.h>
#include<string.h>
int a[20],b[20],n,m;
int sum;
int c;
void swap(int &a,int &b)
{
	int t=a;a=b;b=t;
}
int ak[20],bk[20];
void print(int k)
{
	int i,j;
	for(i=0;i<=k;i++)
	{
		for(j=0;j<bk[i];j++)
		{
			if(i!=0 || j!=0)printf("+");
			printf("%d",a[ak[i]]);
		}
	}
	printf("\n");
	c++;
}


int Search(int k,int s)
{
	int i,j;int beg;
	if(k==0)beg=1;
	else beg=ak[k-1]+1;
	for(i=beg;i<=n;i++)
	{
		for(j=b[i];j>=1;j--)
		{
			ak[k]=i;bk[k]=j;
			int ss=s+a[ak[k]]*bk[k];
			if(ss==sum)print(k);
			else if(ss<sum)Search(k+1,ss);
		}
	}
	return 0;
}




int main()
{
	int i,j,k;
	
	int t;
	while(scanf("%d%d",&sum,&m))
	{
		if(m==0)break;
		memset(b,0,sizeof(b));
		n=1;
		for(i=1;i<=m;i++)
		{
			scanf("%d",&t);
			for(j=1;j<n;j++)if(a[j]==t)break;
			a[j]=t;b[j]++;
			if(j==n)n++;
		}
		n--;
		c=0;
		for(i=1;i<=n;i++)
			for(j=i+1;j<=n;j++)
				if(a[i]<a[j]){swap(a[i],a[j]);swap(b[i],b[j]);}

		printf("Sums of %d:\n",sum);
		Search(0,0);
		if(c==0)printf("NONE\n");

	}
	return 0;
}