// има ли подредица със сума S на масив от положителни цели числа за O(n*S)

#include <iostream>
using namespace std;

const int n = 10, MaxT = 1000;

enum result{ undef, no, yes } memo[n][MaxT];

int a[n] = { 7, 13, 1, 12, 9, 6, 5, 14, 4, 8 };

// можем ли да направим от елемент i нататък сума t
result sum(int i, int t)
{
	if (i == n) return t == 0 ? yes : no;
	if (memo[i][t] != undef) return memo[i][t];
	if (a[i] > t) return memo[i][t] = sum(i + 1, t);
	return memo[i][t] = sum(i + 1, t) == yes || sum(i + 1, t - a[i]) == yes ? yes:no;
}

int main()
{
	for (int i = 0; i < n; i++) for (int j = 0; j < MaxT; j++) memo[i][j] = undef;
	for (int i = 0; i < n; i++) memo[i][0] = yes;

	int S = 29;

	if (sum(0, S) == yes)
	{
		cout << S << endl;
		for (int i = 0; i < n; i++) if (sum(i + 1, S - a[i]) == yes)
		{
			cout << a[i] << " ";
			S -= a[i];
		}
	}

	cout << endl;

	return 0;
}