UVa 11832 - Account Book

#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
using namespace std;

#define MAX_ELEMENT_COUNT 40
#define MAX_ELEMENT_VALUE 1000
#define MAX_SUM 40000

int n;
int element[MAX_ELEMENT_COUNT];
int T[MAX_ELEMENT_COUNT][MAX_SUM + MAX_SUM + 1];

int answer[MAX_ELEMENT_COUNT], pruning_bound;

void addToAnswer(int ways, int i) {
	if (answer[i] == 0)
		answer[i] = ways;
	else if (answer[i] == -ways) {
		answer[i] = 2;
		while (answer[pruning_bound + 1] == 2 && pruning_bound < n)
			pruning_bound++;
	}

}

void buildAnswer(int i, int sum) {
	if (i <= pruning_bound)
		return;
	if (i == 0) {
		addToAnswer(T[i][sum], i);
		return;
	}

	addToAnswer(T[i][sum], i);

	if (T[i][sum] == 1) {
		buildAnswer(i - 1, sum - element[i]);
	} else if (T[i][sum] == -1) {
		buildAnswer(i - 1, sum + element[i]);
	} else if (T[i][sum] == 2) {
		answer[i] = 2;
		buildAnswer(i - 1, sum - element[i]);
		buildAnswer(i - 1, sum + element[i]);
	}
}

int main() {
	int expected_sum;
	scanf("%d%d", &n, &expected_sum);
	while (n != 0 || expected_sum != 0) {
		for (int i = 0; i < n; i++) {
			scanf("%d", &element[i]);
		}

		memset(T, 0, sizeof(T));
		if (element[0] != 0) {
			T[0][MAX_SUM - element[0]] = -1;
			T[0][MAX_SUM + element[0]] = 1;
		} else
			T[0][MAX_SUM - element[0]] = 2;

		vector<int> level[2];
		int next = 0, prev = 1;
		level[next].push_back(MAX_SUM - element[0]);
		level[next].push_back(MAX_SUM + element[0]);
		for (int i = 1; i < n; i++) {
			prev = next;
			next = next ^ 1;
			level[next].clear();
			for (int j = 0; j < level[prev].size(); j++) {

				int generated = level[prev][j] + element[i];
				if (T[i][generated] == 0) {
					level[next].push_back(generated);
					T[i][generated] = +1;
				} else if (T[i][generated] == -1) {
					T[i][generated] = 2;
				}

				generated = level[prev][j] - element[i];
				if (T[i][generated] == 0) {
					level[next].push_back(generated);
					T[i][generated] = -1;
				} else if (T[i][generated] == 1) {
					T[i][generated] = 2;
				}

			}
		}

		if (T[n - 1][MAX_SUM + expected_sum]) {
			memset(answer, 0, sizeof(answer));
			pruning_bound = -1;
			buildAnswer(n - 1, MAX_SUM + expected_sum);
			for (int i = 0; i < n; i++) {
				char ch = answer[i] == -1 ? '-' : (answer[i] == 1 ? '+' : '?');
				printf("%c", ch);
			}
			printf("\n");

		} else
			printf("*\n");

		scanf("%d%d", &n, &expected_sum);
	}

	return 0;
}