pku1564.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#define size 30

int V, N, M, cnt;
int a[size], n[size], p[size];

void Out()
{
	int i, j;
	i = 0;
	while (p[i] == 0)
		i++;
	printf("%d", a[i]);
	for (j = 1; j < p[i]; j++)
	{
		printf("+%d", a[i]);
	}
	i++;
	for (; i < N; i++)
	{
		if (p[i] == 0)
			continue;
		for (j = 0; j < p[i]; j++)
		{
			printf("+%d", a[i]);
		}
	}
	printf("\n");
}

void DFS(int l, int id)
{
	int i;
	if (l == 0)
	{
		Out();
		cnt++;
		return;
	}
	if (l < 0 || id >= N)
	{
		return;
	}
	for (i = n[id]; i >= 0; i--)
	{
		p[id] = i;
		DFS(l - a[id] * i, id + 1);
		p[id] = 0;
	}
}


void Solve()
{
	int x, i;
	memset(a, 0, sizeof(a));
	memset(p, 0, sizeof(p));
	memset(n, 0, sizeof(n));
	scanf("%d", &a[0]);
	n[0] = 1;
	N = 0;
	for (i = 1; i < M; i++)
	{
		scanf("%d", &x);
		if (x == a[N])
		{
			n[N]++;
		}
		else
		{
			a[++N] = x;
			n[N] = 1;
		}
	}
	cnt = 0;
	printf("Sums of %d:\n", V);
	N++;
	DFS(V, 0);
	if (cnt == 0)
	{
		printf("NONE\n");
	}
}

int main()
{
	while (EOF != scanf("%d %d", &V, &M) && (V + M))
	{
		Solve();
	}
	return 0;
}