#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>


// config options
static bool print_recursion = false;
static bool no_output = false;

// algo parameters
static const int max_num_digits = 20;
static int num_digits, min_val, max_val, checksum;

// working vars
static int digits[max_num_digits]; // the result
static int max_cs[max_num_digits], min_cs[max_num_digits]; // helper for faster pruning
static long counter;



bool parseArgs(int argc,char **argv) {
    if (argc<5){printf("Zu wenig Parameter: 1.Anzahl Felder 2.Minwert 3.Maxwert 4.gew�nschte Quersumme\n"); return false;}

    num_digits=strtol(argv[1],0,10);  //Anzahl Felder
    min_val=strtol(argv[2],0,10); // Min Wert
    max_val=strtol(argv[3],0,10); //Maxwert
    checksum=strtol(argv[4],0,10); // gew�nschte Quersumme

    if (num_digits > max_num_digits) {printf("Zuviele Felder\n");return false;}

    if(argc==6){
        char *s = argv[5];
        if(*s=='r') print_recursion=true; //Anzeige der Rekursivaufrufe
        if(*s=='o') no_output=true; //Anzeige ohne Ergebnisausgabe
    }
    return true;
}


void printout() {
    counter++;
    if (no_output) return;
    for (int i=num_digits-1; i>=0; i--) {
        printf(" %d,", digits[i]);
    }
    printf("\n");
}


void listQCombis(int digit, int remaining_cs) {
    if (print_recursion) printf("listQCombis(digits=%d, remaining_cs=%d)\n", digit, remaining_cs);

    // result?
    if (digit==0) {
        if (remaining_cs==0)
            printout();
        return;
    }

    // pruning
    digit--;
    if (remaining_cs > max_cs[digit]) return;
    if (remaining_cs < min_cs[digit]) return;
    
    // recursion
    for (int i=min_val; i<=max_val; i++) {
        digits[digit] = i;
        listQCombis(digit, remaining_cs-i);
    }
}


int main(int argc,char **argv) {
    if (!parseArgs(argc, argv)) return 1;

    // prepare
    counter = 0;
    for (int i = 0; i<num_digits; i++) {
        min_cs[i] = min_val * (i+1);
        max_cs[i] = max_val * (i+1);
    }

    // recurse
    listQCombis(num_digits, checksum);
    printf("%lu Kombinationen gefunden \n",counter);
}