Partizioni

/*[Partizioni]. Scrivere una funzione ricorsiva che preso in input un
intero n conta il numero di combinazioni, contenenti solo numeri positivi (maggiori
di 0) minori o uguali ad n ed ordinati in modo crescente, tali che la loro somma faccia
1
n. Se ad esempio n = 3, le combinazioni, contenenti numeri positivi minori o uguali
a tre ed ordinati in modo crescente (ogni numero `e minore o uguale al successivo),
tali che la loro somma faccia 3, sono:
111
12
3
Quindi ci sono tre diverse combinazioni che hanno somma 3. Nota bene che 12 `e
corretta ma 21 non `e ordinata.
Se ad esempio n = 4, le combinazioni ordinate contenenti numeri minori o uguali a
quattro, tali che la loro somma faccia 4, sono:
1111
112
13
22
4
Quindi abbiamo 5 diverse combinazioni.*/

#include

int partition(int n, int k);

int main()
{
int n;
int somma=0;
scanf("%d",&n);
printf("%d",partition(n,1));
return 0;
}

int partition(int n, int k)
{
if (k > n) return 0;
if (k == n) return 1;
else
return partition(n, k+1) + partition(n-k, k);
}