3191861_wa.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 94 行

#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>

using namespace std;

int dp[1001][13];
int sum, n, num[13], Sum[13];

bool cmp(int a,int b)
{
	return a > b;
}

int mark[13];

string last, now;

void out()
{
	int i, f;
	char str[5];

	f = 0;
	for(i = 0; i < n; i++)
	{
		if(mark[i])
		{
			if(f==1)
				now += "+";
			else
				f = 1;
			now += itoa(num[i],str,10);
		}
	}
	if(last==""||last!=now)
		cout << now << endl;
	last = now;
}

void dfs(int p,int s)
{
	int i;

	if(s > sum)
		return ;
	if(s == sum)
	{
		now = "";
		out();
		return ;
	}
	if(s + Sum[p] < sum)
		return ;
	for(i = p; i < n; i++)
	{
		mark[i] = 1;
		dfs(i+1,s+num[i]);
		mark[i] = 0;
	}
}

int main()
{
	int i;

	while(scanf("%d%d",&sum,&n)==2)
	{
		if(sum==0&&n==0)
		{
			break;
		}
		printf("Sums of %d:\n",sum);
		last = "";
		for(i = 0; i < n; i++)
		{
			scanf("%d",&num[i]);
		}
		memset(mark,0,sizeof(mark));
		sort(num,num+n,cmp);
		Sum[n] = 0;
		for(i = n-1; i >= 0; i--)
		{
			Sum[i] = Sum[i+1]+num[i];
		}
		dfs(0,0);
		if(last=="")
			puts("NONE");
	}
	return 0;
}