plata sumei S cu N monede

//Se citesc valorile a N monede (printre ele exista si moneda de valoare 1, pentru a ne asigura
//ca se poate realiza plata). Sa se genereze toate modalitatile de a plati o suma S, folosind
//cele N monede.


#include <stdio.h>

int S, n, st[1000], x[100];

int valid(int p)
{
    if (p>1)
        if (st[p]<st[p-1])
        return 0;

    int i, s = 0;

    for (i = 1; i <= p; i++)
        s = s + st[i];

    if (s > S)
        return 0;

    return 1;
}

int solutie (int p)
{
    int i, s = 0;

    for (i = 1; i <= p; i++)
        s = s + st[i];

    if (s == S)
        return 1;

    return 0;
}

void afis(int p)
{
    int i;

    for (i = 1; i <= p; i++)
        printf("%d ",st[i]);

    printf("\n");
}

void backtr(int p)
{
    int i;

    for (i=0; i<=n; i++)
    {
        st[p] = x[i];

        if (valid(p))
            if (solutie(p))
                afis(p);
            else
                backtr(p+1);
    }
}

int main()
{

    FILE *fin;
    fin = fopen("date.in","r");

    int i;

    fscanf(fin,"%d",&n);

    x[0] = 1;
    for (i = 1; i <= n; i++)
        fscanf(fin,"%d",&x[i]);

    fscanf(fin,"%d",&S);

    backtr(1);

    return 0;
}

// varianta 2, comentata

//Se citesc valorile a N monede (printre ele exista si moneda de valoare 1, pentru a ne asigura
//ca se poate realiza plata). Sa se genereze toate modalitatile de a plati o suma S, folosind
//cele N monede.
//In date.in ordinea este: N \n monedele... \n S

#include <stdio.h>

int S, n, st[1000], x[100]; // n - numarul de monede, st - stiva, x - vectorul in care sunt memorate monedele

int valid(int p)
{
    if (p>1)
        if (st[p]<st[p-1]) // am ales sa afisez mondele in ordine crescatoare, lexicografica
        return 0; // daca nu sunt in ordine crescatoare nu e valid

    int i, s = 0;

    for (i = 1; i <= p; i++)
        s = s + st[i];

    if (s > S) // daca suma monedelor este mai mare decat suma S data atunci nu e valid
        return 0;

    return 1;
}

int solutie (int p)
{
    int i, s = 0;

    for (i = 1; i <= p; i++)
        s = s + st[i];

    if (s == S) // pentru a fi solutie suma mondelor trebuie sa fie egala cu suma S data
        return 1;

    return 0;
}

void afis(int p)
{
    int i;

    for (i = 1; i <= p; i++)
        printf("%d ",st[i]);

    printf("\n");
}

void backtr(int p)
{
    int i;

    for (i=0; i<=n; i++)
    {
        st[p] = x[i];

        if (valid(p))
            if (solutie(p))
                afis(p);
            else
                backtr(p+1);
    }
}

int main()
{

    FILE *fin;
    fin = fopen("date.in","r");

    int i;

    fscanf(fin,"%d",&n);

    x[0] = 1; // moneda 1 este implicit folosita
    for (i = 1; i <= n; i++)
        fscanf(fin,"%d",&x[i]); // citim monezile

    fscanf(fin,"%d",&S);

    backtr(1);

    return 0;
}