首页 > 代码库 > hdu 1258 Sum It Up(dfs)

hdu 1258 Sum It Up(dfs)

# include <stdio.h>
# include <algorithm>
using namespace std;
int flag,t,n,a[10010],cot[10010],vis[100010];
void dfs(int x,int sum,int count)
{
	int i;
	if(sum>t)
		return ;
	else if(sum==t)
	{
		
		for(i=0;i<count;i++)
		{
			if(i!=count-1)
				printf("%d+",cot[i]);
			else
				printf("%d\n",cot[i]);
		}
		flag=1;
		return ;//每个return 都是返回到调用当前dfs的那个dfs的语句的末尾//上个dfs
	}
	int tmp=-1;
	for(i=x;i<n;i++)
	{
		if(a[i]!=tmp)
		{
			cot[count++]=a[i];
		    tmp=a[i];//保留当前的数,能避免重复
		    dfs(i+1,sum+a[i],count);
			count--;
		}
	}
}
int main()
{
	while(~scanf("%d%d",&t,&n),t+n)
	{
		memset(a,0,sizeof(a));
		for(int i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
		}
		flag=0;
		memset(vis,0,sizeof(vis));
		memset(cot,0,sizeof(cot));
		printf("Sums of %d:\n",t);
		dfs(0,0,0);
		if(!flag)
		printf("NONE\n");
	}
	return 0;
}

hdu 1258 Sum It Up(dfs)