#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[]);
bool ZnajdzSumePar(int rozwiazanie[], int zbior[], int it, int *sumapar, int wielkosc, int *gdzie);
bool ZnajdzSumeCalkowita(int rozwiazanie[], int zbior[], int it, int *suma, int wielkosc, int *gdzie);
void wypisz(int rozwiazanie[], int zbior[], int wielkosc, int ilosc,int start);

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;
}
bool ZnajdzSumePar(int rozwiazanie[], int zbior[], int it, int *sumapar, int wielkosc, int *gdzie)
{
	*sumapar = rozwiazanie[it] + rozwiazanie[it - 1];
	for (int s = 0; s < wielkosc; s++)
	{
		if (*sumapar == zbior[s])
		{

			*gdzie = s;
			return true;
		}
	}
	return false;
}

bool ZnajdzSumeCalkowita(int rozwiazanie[], int zbior[], int it, int *suma, int wielkosc, int *gdzie)
{
	*suma += rozwiazanie[it];
	for (int s = 0; s < wielkosc; s++)
	{
		if (*suma == zbior[s])
		{

			*gdzie = s;
			return true;
		}
	}
	suma -= rozwiazanie[it];
	return false;
}
void wypisz(int rozwiazanie[], int zbior[], int wielkosc, int ilosc,int start)
{
	//=====================================================
	cout << "\n\n rozwiazanie" << start << "\n";
	for (int x = 0; x <= ilosc; x++)
		cout << rozwiazanie[x] << " ";
	cout << "\n";
	for (int x = 0; x < wielkosc; x++)
		cout << zbior[x] << " ";
	//====================================================
}
void mapuj(int rozwiazanie[], int zbior[], int ilosc, int wielkosc, int start, int suma, bool &jest)
{
	int gdziePara=0, gdzieSuma=0;
	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 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[start] = zbior[j];//dodajemy potencialne rozwiazanie
			zbior[j] = 0;
			wypisz(rozwiazanie, zbior, wielkosc, ilosc, start);//wypisanie
			int sumapar = 0;
			if (ZnajdzSumePar(rozwiazanie, zbior, start, &sumapar, wielkosc, &gdziePara))
			{
				zbior[gdziePara] = 0;
				wypisz(rozwiazanie, zbior, wielkosc, ilosc, start);//wypisanie
				if (ZnajdzSumeCalkowita(rozwiazanie, zbior, start, &suma, wielkosc, &gdzieSuma))
				{
					zbior[gdzieSuma] = 0;
					wypisz(rozwiazanie, zbior, wielkosc, ilosc, start);//wypisanie
					mapuj(rozwiazanie, zbior, ilosc, wielkosc, ++start, suma, jest);
					zbior[gdzieSuma] = suma;
					suma -= rozwiazanie[start];
				}
				zbior[gdziePara] = sumapar;
				sumapar = 0;
			}
			zbior[j] = rozwiazanie[start];//to nie to wiec zwracamy
			rozwiazanie[start] = 0;
		}

}