CODEWITHSUNDEEP
c++recursion
Parth Patel
Parth Patel

Reputation: 75

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);

}

please help...

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);
}

}

Upvotes: 3

Views: 4260

Answers (1)

novice
novice

Reputation: 545

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);
}

Inspired from: http://www.programminglogic.com/integer-partition-algorithm/

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

Upvotes: 5

Related Questions