Parth Patel - 1 month ago 7
C++ Question

# computes the number of ways to partition n into the sum of positive integers c++

I need to write function as part of assignment..
I need to compute the number of ways to partition n into the sum of positive integers and I can't use for while or goto

``````/*
* REQUIRES: n > 0
* EFFECTS: computes the number of ways to partition n into the sum of
*          positive integers
* MUST be tree recursive
* Hint: Use a helper function that computes the number of ways to
* partition n using a bounded subset of integers. Then use logic
* similar to count_change() from lecture to divide partitions into
* those that use a specific item and those that do not.
*/
int num_partitions(int n);
``````

I figured a way to print them but unable to count it and my function also needed for loop. Here's function

``````void print(int n, int * a) {
int i ;
for (i = 0; i <= n; i++) {
printf("%d", a[i]);
}
printf("\n");
}

int integerPartition(int n, int * a, int level,int c){
int first;
int i;
if (n < 1)
{
return c;
}
a[level] = n;
print(level, a);
c++;
first = (level == 0) ? 1 : a[level-1];
for(i = first; i <= n / 2; i++){
a[level] = i;
integerPartition(n - i, a, level + 1,c);
}
}
int num_partitions(int n){
int * a = (int * ) malloc(sizeof(int) * n);
return integerPartition (n, a, 0,0);

}
``````

here is the count change function

``````int count_change(int amount, const int coins[], int num_coins) {

if (amount == 0) {

return 1;

} else ifâ€‹ (amount < 0 || num_coins < 1) {

return 0;

} else {

return
count_change(amount - coins[num_coins - 1], coins, num_coins) +

count_change(amount, coins, num_coins - 1);
}

}
``````

You can do it like this:

``````#include <conio.h>
#include <iostream>

using namespace std;
int integerPartition(int n, int k);

int main()
{
int n;
cin>>n;
int k =n;
cout<<integerPartition(n,k);

getchar();
return 0;
}
int integerPartition(int n, int k)
{
if(k==0)
return 0;
if(n ==0)
return 1;
if(n<0)
return 0;

return integerPartition(n,k-1) + integerPartition(n-k,k);
}
``````

or you can also use: recurrence formula for partition functions, given on
https://en.wikipedia.org/wiki/Partition_(number_theory)