UVa – 574 – Sum it Up

Problem Link : UVa – 574 – Sum it Up

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

using namespace std;

int a[50], s[50], N, E;

int dfs(int left, int index, int length) {
	int success = 0;
	if (index >= N || left < 0)	return 0;
	left -= a[index], s[length++] = a[index++];
	if (left == 0) {
		for (int i = 0; i < length; i++)
			printf("%d", s[i]), printf(i != length - 1 ? "+" : "\n");
		return 1;
	}
	for (int i = index; i < N; i++)
		if (!(i - index) || a[i] != a[i - 1])
			success += dfs(left, i, length);
	return success;
}

int main() {
	int left;
	while (scanf("%d %d", &left, &N) && left && N) {
		int i, success = 0;
		for (i = 0; i < N; i++)	scanf("%d", &a[i]);
		sort(a, a + N), reverse(a, a + N);
		printf("Sums of %d:\n", left);
		for (i = 0; i < N; i++)
			if (!i || a[i] != a[i - 1])
				success += dfs(left, i, 0);
		if (!success)	printf("NONE\n");
	}
	return 0;
}

Advertisements

One thought on “UVa – 574 – Sum it Up

  1. Braulio Acosta says:

    Great solution!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: