#include <iostream>
#include <conio.h>
#include <fstream>
#include <string>
#include <vector>
using namespace std;

void wczytaj(int zbior[], int wielkosc);
void preload(int &wielkosc);
bool spr(int liczbaciec, int wielkosc);
int ZnajdzMaxWartosc(int wielkosc, int zbior[]);
void mapuj(int rozwiazanie[], int zbior[], int ilosc, int wielkosc, int start, int suma,bool &jest);
int ZnajdzSubMaxWartosc(int max, int wielkosc, int zbior[]);

int max;

int main()
{
	int *zbior, *rozwiazanie;
	int LiczbaCiec = 0, WielkosZbioru = 0;
	bool jest = false;

	cout << "podaj ilosc ciec: " << endl;
	cin >> LiczbaCiec;
	cout << endl;
	preload(WielkosZbioru);
	zbior = new int[WielkosZbioru];
	wczytaj(zbior, WielkosZbioru );

	if (spr(LiczbaCiec, WielkosZbioru))
	{
		cout << " dane wejsiowe poprawne" << endl;

		rozwiazanie = new int[LiczbaCiec + 1];
		for (int i = 0; i < LiczbaCiec; i++)
			rozwiazanie[i] = 0;

		max = ZnajdzMaxWartosc(WielkosZbioru, zbior);
		int submax = ZnajdzSubMaxWartosc(max, WielkosZbioru, zbior);
		rozwiazanie[0] = max - submax;

		for (int i = 0; i <= WielkosZbioru; i++)
			if (rozwiazanie[0] == zbior[i])
			{
				zbior[i] = 0;
				break;
			}

		cout << "\n\n";
		for (int x = 0; x < LiczbaCiec; x++)
			cout << rozwiazanie[x] << " ";
		cout << "\n";
		for (int x = 0; x < WielkosZbioru; x++)
			cout << zbior[x] << " ";
		//mapowanie
		mapuj(rozwiazanie, zbior, LiczbaCiec, WielkosZbioru, 1, 3, jest);
		if(!jest)
			cout << "\n brak rozwiazania\n";
	}
	else
		cout << "\n bledne dane wejsciowe\n";

	_getch();
	return 0;
}
void preload(int &wielkosc)
{
	fstream plik;
	string dane;
	int j = 0;
	//============		preload
	plik.open("test.txt", ios::in);
	while (!plik.eof())
	{
		getline(plik, dane, ' ');
		wielkosc++;
	}
	plik.close();
}
void wczytaj(int zbior[], int wielkosc)
{
	fstream plik;
	string dane;
	int j = 0;
	plik.open("test.txt", ios::in);
	plik.clear();
	plik.seekg(0, ios::beg);

	for (int i = 0; i < wielkosc; i++)
	{
		getline(plik, dane, ' ');
		zbior[i] = atoi(dane.c_str());
	}


	plik.close();
	//wielkosc -= 1;
}
bool spr(int c, int wielksoc)
{
	double s1 = 1, s2 = 1;

	for (int i = 1; i <= c; i++)
		s1 *= i;
	for (int i = 1; i <= c + 2; i++)
		s2 *= i;
	cout << s1 << " " << s2 << " " << wielksoc<< " " << s2 / (2 * s1) << endl;
	if (wielksoc  == s2 / (2 * s1))
		return true;
	else return false;
}
int ZnajdzMaxWartosc(int c, int zbior[])
{
	int maxi = 0;
	for (int i = 0; i <= c; i++)
	{
		if (maxi<zbior[i])
			maxi = zbior[i];

	}
	return maxi;
}
int ZnajdzSubMaxWartosc(int maxi, int c, int zbior[])
{
	int semimaxi = 0;
	for (int j = 0; j < c; j++)
	{
		if (zbior[j]>semimaxi && zbior[j] < max)
			semimaxi = zbior[j];
	}
	return semimaxi;
}
void mapuj(int rozwiazanie[], int zbior[], int ilosc, int wielkosc, int start, int suma, bool &jest)
{
	if (start > ilosc && suma == max)
	{
		cout << "\n\nROZWIAZANIE\n";
		for (int x = 0; x < ilosc; x++)
			cout << rozwiazanie[x] << " ";
		cout << "\n";
		for (int x = 0; x < wielkosc; x++)
			cout << zbior[x] << " ";
		jest = true;
		return;
	}
	else if (start == ilosc && suma != max)
		return;
	if (jest)
		return;
	else for (int i = start; i <= ilosc; i++)
	{
		for (int j = 0; j < wielkosc; j++)
		{
			while (zbior[j] == 0)
				j++;
			if (suma + zbior[j] > max)// jak bedzie za duzo to skracamy poszukiwanie i przechodzimy dalej
				continue;
			rozwiazanie[i] = zbior[j];//dodajemy potencialne rozwiazanie
			zbior[j] = 0;
			int sumapar = rozwiazanie[i] + rozwiazanie[i - 1];
			for (int s = 0; s < wielkosc;s++)
			{
				if (sumapar == zbior[s])
				{
					//if (i - 1 != 0)
						zbior[s] = 0; // znalezlismy to usuwamy z potencialnych rozwiazan
					suma += rozwiazanie[i];
					for (int ss = 0; ss < wielkosc; ss++)
					{
						if (suma == zbior[ss])
						{

							zbior[ss] = 0;//usuwamy z potencialnych rozwiazan
							 //=========================================
							cout << "\n";
							for (int x = 0; x < ilosc; x++)
								cout << rozwiazanie[x] << " ";
							cout << "\n";
							for (int x = 0; x < wielkosc; x++)
								cout << zbior[x] << " ";
							//=========================================
							mapuj(rozwiazanie, zbior, ilosc, wielkosc, ++i, suma, jest);
							zbior[ss] = suma;// to nie to wiec zwracamy
							break;
						}
					}
					suma -= rozwiazanie[i];
					zbior[s] = sumapar;// to nie to wiec zwracamy
					break;
				}
			}
			zbior[j] = rozwiazanie[i];//to nie to wiec zwracamy
			rozwiazanie[i] = 0;
		}
	}
}