Partitions into summands#2390

Partitions into summands (Editorial)

Let $n = x_{1} + x_{2} + ... + x_{k}$ n = x_1 + x_2 + ... + x_k be a partition of the number $n$ into natural summands. According to the problem statement, the summands in any partition must satisfy the inequality:

x_{1} \geq x_{2} \geq ... \geq x_{k}

x_1 \ge x_2 \ge ... \ge x_k

The first summand $x_{1}$ x_1 can take values from $1$ to $n$ , and each subsequent $x_{i} (2 \leq i \leq k)$ x_i~(2 \le i \le k) can take values from $1$ to $x_{i - 1}$ x_{i-1}.

The recursive idea behind the partition generation procedure is as follows: if, when partitioning the number $n$ , the first summand $x_{1} (x_{1} \leq n)$ x_1~(x_1 \le n) is chosen, then one should recursively generate all possible partitions of the number $n - x_{1}$ n - x_1 into summands that do not exceed $x_{1}$ x_1.

Algorithm implementation

We'll use the array $x$ to generate the partitions of the number $n$ .

int x[50];

The function f generates the partitions of the number $n$ and takes three arguments:

$p os$ — the current position in the array $x$ ;
$ma x$ — the maximum allowed value of the summand that can be placed at position $p os$ ;
$n$ — the current value of the number to be partitioned.

void f(int pos, int max, int n)
{

If the value of $n$ becomes zero, it means the partition is complete, and the current contents of the array $x$ represent one of the partitions. In this case, we print the array.

  if (n == 0)
  {
    for (int i = 0; i < pos; i++) 
      printf("%d ", x[i]);
    printf("\n");
    return;
  }

C++

At position $p os$ of the array $x$ , any number from $1$ to $min (ma x, n)$ min(max, n) can be placed.

  for (int i = 1; i <= min(max, n); i++)
  {
    x[pos] = i;
    f(pos + 1, i, n - i);
  }
}

The main part of the program. Read the input value $n$ and start the function to generate all possible partitions of this number.

scanf("%d",&n);
f(0,n,n);