prob5.cpp

#include <iostream>
#include <vector>
#include <map>
#include <utility>

using namespace std;

vector <int> divisors;
map < pair< int, pair<bool, int> >, int > DP;
vector<int> ans;

bool solve (int curr, bool toAdd, int n, vector<int> currSum) {
	if (DP.find( {curr, {toAdd, n} } ) != DP.end() ) return DP[{curr, {toAdd, n} }];
	if (n == 0) {
		ans = currSum;
		return DP[{curr, {toAdd, n} }] = true;
	}
	if (divisors[curr] > n || curr >= divisors.size()) return DP[{curr, {toAdd, n} }] = false;

	bool solved = false;

	if (toAdd) {
		currSum.push_back(curr);
		solved |= solve(curr+1, true, n-divisors[curr], currSum);
		solved |= solve(curr+1, false, n-divisors[curr], currSum);
	} else {
		solved |= solve(curr+1, true, divisors[curr], currSum);
		solved |= solve(curr+1, false, divisors[curr], currSum);
	}

	return DP[{curr, {toAdd, n} }] = solved;
}

int main(void) {
	int n;
	cin >> n;

	while (n != -1) {

		for (int i = 1; i < n; i++) {
			if (n % i == 0) {
				divisors.push_back(i);
				cout << i << " ";
			}

		}
		cout << endl;

		bool solved = false;

		vector<int> temp;

		solved |= solve(0, true, n, temp);
		solved |= solve(0, false, n, temp);

		if (solved) {
			cout << n << " = ";
			for (int i = 0; i < ans.size(); i++) {
				cout << divisors[ans[i]];
				if (i != ans.size() - 1) cout << " + ";
			}
			cout << endl;
		} else {
			cout << n << " is NOT perfect." << endl;
		}

		divisors.clear();
		DP.clear();
		cin >> n;
	}


}