Example code for integer partition problem (recursion) in C language

Example code for integer partition problem (recursion) in C language

The integer partition problem is one of the classical propositions in the algorithm, and it will be covered almost all the time when it comes to recursion. The so-called integer partition means that a positive integer n is written as follows:

n = m1 + m2 +... + mi; (where mi is a positive integer and 1 < = mi < = n), then {m1,m2... ,mi} is a partition of n.

If {m1, m2,... The maximum value in mi} does not exceed m, that is, max(m1,m2,... , mi) < =m, then it is said to belong to an m partition of n. Here we remember that the number of m partitions of n is f(n,m);

But when n = 4, for example, he has five divisions, {4}, {3, 1}, {2}, {2,1,1}, {1,1,1,1};

Notice that 4=1+3 and 4=3+1 are considered partitions of the same 1.

The problem is to find the number of partitions of n, that is, f(n, n). So let's think about f(n,m);

1. Recursive method:

According to the relationship between n and m, consider the following situations:

(1) when n=1, no matter what the value of m is (m) > 0), there is only one partition, namely {1};

(2) when m=1, no matter what the value of n is, there is only one division, that is, n 1, {1,1,1... , 1};

(3) when n=m, there are two situations according to whether n is included in the partition:

(a) contains the case of n, only one is {n};

The (b) partition does not include the case of n, in which case the largest number in the partition must be 1 less than n, that is, all (n-1) partitions of n.

So f(n,n) =1 + f(n, n-1);

(4) when n < When it comes to m, it is equivalent to f(n,n), since it is impossible to have a negative number in the partition.

(5) but n > When m is used, it can be divided into two situations according to whether the maximum m is included in the partition:

(a) partition contains the case of m, that is, {m, {x1,x2... xi}}, {x1, x2,... The sum of xi} is n-m, so this is the case

For f (n - m m)

In the case that m is not included in the partition (b), all values in the partition are smaller than m, that is, the partition of n (m-1) is f(n, m-1).

So f(n, m) = f(n-m, m)+f(n, m-1);

To sum up,

       f(n, m)=  1;       (n=1 or m=1)

        f(n,m)  =  f(n, n);          (n<m)

               1+ f(n, m-1);       (n=m)

               f(n-m,m)+f(n,m-1);     (n>m)

#include<iostream>
using namespace std;

int equationCount(int n,int m)
{
  if(n==1||m==1)
    return 1;
  else if(n<m)
    return equationCount(n,n);
  else if(n==m)
    return 1+equationCount(n,n-1);
  else
    return equationCount(n,m-1)+equationCount(n-m,m);
}

int main(void)
{
  int n;
  while(scanf("%d",&n)!=EOF&&(n>=1&&n<=120))
  {
    printf("%d\n",equationCount(n,n));
  }
  return 0;
}

Thank you for reading, I hope to help you, thank you for your support of this site!