sum it up(dfs生成不重复组合).cpp

来自「杭电acm解题报告2001---2099.」· C++ 代码 · 共 60 行

#include <cstdio>

int sum,n,len,m;
int num[20],pre[20];
bool flag;

void print()
{
	flag=true;
	int i;
	for(i=0; i<len; i++)
	{
		if(i)
			printf("+");
		printf("%d", pre[i]);
	}
	printf("\n");
}

void dfs(int d, int all)
{
	int i;
	len++;
	if(sum == all)
		print();
	else
	{
		
		for(i=d+1;i<n; i++)
		{
			if(num[i]+all<=sum && num[i]!=m)
			{
				pre[len] = num[i];
				dfs(i, all + num[i]);
			}
		}
	}
	if(d != -1)
		m = num[d];
	len--;
}

int main()
{
	int i,j;
	
	while(scanf("%d %d",&sum,&n))
	{
		if(sum==0 && n==0)
			break;
		for(i=0;i<n;i++)
			scanf("%d",&num[i]);
		printf("Sums of %d:\n",sum);
		flag=false;
		m=0;len=-1;
		dfs(-1,0);
		if(!flag)
			printf("NONE\n");
	}
}