#include "gerechte_erbschaft.h"
#include <iostream>
using namespace std;

// nur modulweit bekannte Variablen

const int* erbe; // eigentlich ein Array, aber wir kennen die Größe a priori nicht
// der Zugriff *erbe ist gleichbedeutend mit erbe[0]
// ein Array ist intern immer ein Pointer auf den ersten Eintrag 
bool* inErbeEins; // dito, ein Array, das anzeigt, welche Werte im Erbe 1 sind
int size;
int gesamterbe; // für die dyn.-Prog.-Variante

void verteile_erbe(const int erbteil, const int summeErbeEins, const int summeErbeZwei);
// Vorwärtsdeklaration der lokalen Funktion

void gerechte_erbschaft(const int erbe_pa[], const int size_pa) {
     // erbe_pa : Zeiger auf der erste Element des Arrays der Erbteile
     // size_pa : Anzahl der Elemente
     erbe=erbe_pa; // für die anderen Funktionen im Modul sichtbar machen
     size=size_pa; // für die anderen Funktionen im Modul sichtbar machen
     inErbeEins=new bool[size_pa]; // Initialisierung hier nicht nötig
     verteile_erbe(0,0,0);
     delete inErbeEins; // Speicher wieder freigeben
}

void verteile_erbe(const int erbteil, const int summeErbeEins, const int summeErbeZwei) {
     if (erbteil==size) {
        if (summeErbeEins==summeErbeZwei) {
            cout << "Neue Loesung:" << endl << "Erstes Erbe: ";
            for(int i=0;i<size;i++) {
                if (inErbeEins[i]) {
                  cout << erbe[i] << ", ";
                }
            }
            cout << "zweites Erbe: ";
            for(int i=0;i<size;i++) {
                if (!inErbeEins[i]) {
                  cout << erbe[i] << ", ";
                }
            }
            cout << "suche weitere Loesungen ..." << endl;
        } // else alle Elemente verteilt, aber keine gerechte Aufteilung
     } else {
       inErbeEins[erbteil]=true;
       verteile_erbe(erbteil+1,summeErbeEins+erbe[erbteil],summeErbeZwei);
       inErbeEins[erbteil]=false;
       verteile_erbe(erbteil+1,summeErbeEins,summeErbeZwei+erbe[erbteil]);
     }
}

void gerechte_erbschaft_dynprog(const int erbe_pa[], const int size_pa) {
     // erbe_pa : Zeiger auf der erste Element des Arrays der Erbteile
     // size_pa : Anzahl der Elemente
     gesamterbe=0;
     int i,j;
     for(i=0;i<size_pa;i++) {
         gesamterbe+=erbe_pa[i];
     }
     if (gesamterbe%2==0) { // was passiert, wenn man die Abfrage weglässt?
         int zielwert=gesamterbe/2;
         bool* erreichbar=new bool[zielwert+1];
         erreichbar[0]=true;
         for(i=1;i<=zielwert;i++) {
             erreichbar[i]=false;
         }
         for(j=0;j<size_pa;j++) {
           for(i=zielwert-erbe_pa[j];i>=0;i--) { // rückwärts, damit Erbteil
             if (erreichbar[i]) {                // nur 1 mal verwendet wird
               erreichbar[i+erbe_pa[j]]=true;
         } } }
         if (erreichbar[zielwert]) {
           cout << "Es gibt ein gerechtes Erbe" << endl;
         } else {
           cout << "Es gibt kein gerechtes Erbe" << endl;
         }
         delete erreichbar; // Speicher wieder freigeben
     } else {
       cout << "Es gibt kein gerechtes Erbe" << endl;
     }
}