descompunere numere bkt

//Descompunerea unui numar natural ca suma de numere naturale nenule, cu urmatoarele variante:
//a. descompuneri distincte

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

int n = 15, x[101];

void bkt(int k)
{
    int i, v, s;

    for (v = x[k-1]; v <= n - k + 1; v++)
    {
        x[k] = v;
        s = 0;
        for (i = 1; i <= k; i++)
            s = s + x[i];

            if (s <= n)
                if (s == n)
                    {
                        for (i = 1; i <= k; i++)
                            printf("%d ",x[i]);
                        printf("\n");
                    }
                else bkt(k + 1);
    }
}


int main()
{
    x[0] = 1;
    bkt(1);

    return 0;
}


//b. descompuneri distincte cu termeni distincti.
#include <stdio.h>

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

int valid(int p)
{
    int i;

    if (p > 1)
        if (st[p] < st[p-1] || st[p] == st[p-1]) // se verifica ordinea crescatoare
        return 0;

    int s = 0;

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

    if (s > n)
        return 0;

    return 1;
}

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

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

    if (s == n)
        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=1; i<=n; i++)
    {
        st[p] = i;

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


int main()
{
    scanf("%d",&n);

    backtr(1);

    return 0;
}

// varianta cu comentarii
//Descompunerea unui numar natural ca suma de numere naturale nenule, cu urmatoarele variante:
//a. descompuneri distincte
//b. descompuneri distincte cu termeni distincti.
#include <stdio.h>

int n, st[100]; // n - numarul care va fi descompus, st - stiva

int valid(int p)
{
    int i;

    if (p > 1) // pentru punctul b) doar adaugam in if-ul de mai jos conditia "|| st[p] == st[p-1]", iar pentru a) o scoatem
        if (st[p] < st[p-1] || st[p] == st[p-1]) // se verifica ordinea crescatoare si ca termenii unei descompuneri sa fie distincti ( in cazul punctului b)
        return 0;

    int s = 0;

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

    if (s > n) // se verifica ca nu cumva suma din stiva sa depaseasca numarul
        return 0;

    return 1;
}

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

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

    if (s == n) // pentru a fi solutie trebuie ca Ssuma din stiva sa fie egala cu n
        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=1; i<=n; i++)
    {
        st[p] = i;

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


int main()
{
    scanf("%d",&n);

    backtr(1);

    return 0;
}