3191965_ac_0ms_268k.cpp

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

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#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];
vector <string> ans;
string 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);
		}
	}
	ans.push_back(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, j;

	while(scanf("%d%d",&sum,&n)==2)
	{
		if(sum==0&&n==0)
		{
			break;
		}
		ans.clear();
		printf("Sums of %d:\n",sum);
		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(ans.empty())
			puts("NONE");
		else
		{
			int used[1000];

			memset(used,0,sizeof(used));
			for(i = 0; i < ans.size(); i++)
			{
				if(used[i])
					continue;
				else
				{
					cout << ans[i] << endl;
					for(j = i+1; j < ans.size(); j++)
					{
						if(strcmp(ans[i].c_str(),ans[j].c_str())==0)
							used[j] = 1;
					}
				}
			}
		}
	}
	return 0;
}