Ex24 Bun

#include <stdio.h>
#include <stdlib.h>
/*
 Am eliminat posibilitatile de genul 1 2 1 , 2 1 1, 1 1 2
 E bazat pe un vector de pointer
 Am sortat reperele si dupa am lucrat cu ajutoul vectroului de pointeri
 Am optimizat memoria mult, si numarul de cazuri posibile l-am redus
 Sper ca e bine ca am eliminat cazurile de la inceput.
*/

unsigned valid(unsigned short * rep, unsigned short**st, unsigned short n, unsigned short varf) { // vedem daca adresa fiecarul element din repre se gaseste in vectorul st
    unsigned short i, j, ok;
    for (i = 1; i <= n; i++) {
        ok = 1; // initializam cu 1 pentru fiecare element din repere
        for (j = 1; j <= varf; j++)
            if (rep + i == *(st + j)) { // daca gasim
                ok = 0; // deoarece am gasit un element variabila devine  0
                break; // parasim for deoarece am verificat ce ne trbuia
            }
            if (ok) return 0; // daca nu s-a gasit un element oprim functia si afisam rezultatul

    }
    return 1; // altfel toate elemtnele din repere se gasesc in st
}

int main() {
    unsigned short L, n, suma, i, varf, *stiva[1001]; // Lungigime numar de repre varf deoarece utilizam principi din stiva, si un vector de pointeri
    unsigned short repere[11]; // salvam lungimile reperelor
    FILE *f; // variabila de tip fiser
    f = fopen("in.txt", "r"); // deschidem in mod citire
    fscanf(f, "%hu%hu", &L, &n); // citim lungimea si numarul de repere
    for (i = 1; i <= n; i++)
        fscanf(f, "%hu", &repere[i]); // citim lungimea reperelor
    fclose(f);// inchidem fiserul
    do {  // Bubble sort
        suma = 0; // contor
        for (i = 1; i <= n; i++)
            if (repere[i] > repere[i + 1])
                suma = 1, repere[i] ^= repere[i + 1], repere[i + 1] ^= repere[i], repere[i] ^= repere[i + 1]; // bubule sort prin interclasare daca tot am facut biti
    } while (suma);
    // Se pot aloca vectori de pointer dinamic? pentru ca avem nevoie de o stiva de L/repere[1] + 2 si sa nu fac risipa
    suma = repere[1];// initializari
    varf = 1;
    stiva[0] = repere + varf; // sa nu am eroare cand varf = 0
    stiva[varf] = repere + varf;// initializari
    f = fopen("out.txt", "w");
    while (varf) { // se opreste cand stiva este goala
        if (suma < L) // daca suma este mai mica adaugam adresa varfului la varf urmator si adunam la suma
            stiva[varf + 1] = stiva[varf], suma += *stiva[varf++]; // adauagm adresa elementului curent pana suma este >= L
        else { // altfel
            if (suma == L  && valid(repere, stiva, n, varf)) { // daca suma = L si functia de valid returneaza 1 se afiseaza
                for (i = 1; i <= varf; i++)
                    fprintf(f, "%hu ", *stiva[i]);// afisam elementele de la adresele indicate de st
                fprintf(f, "\n");
            }
            suma -= *stiva[varf--]; // scadem din suma actual varf dupa care scadem varful
            suma -= *stiva[varf]; //scadem din suma noul varf
            stiva[varf]++; //noului varf i se atrebuie adresa urmatorul element din repere
            suma += *stiva[varf]; // se adauga valoarea elementului din repere
        }

    }
    fclose(f);
    return 0;
}