Grade 11 · BacktrackingCitește în română

Partitions of a natural number

Original: Partițiile unui număr natural

ExponentialC++1763 lines1 example

The idea

Prints all ways of writing n as a sum of non-zero natural numbers, where the order of the terms does not matter. To avoid repeating the same decomposition, the terms are generated in increasing order (x[k] ≥ x[k - 1]). We keep how much of n is left: a term is valid if it does not exceed the remainder, and the solution is complete when the remainder becomes 0.

Original description (Romanian)

Afișează toate modurile de a scrie n ca sumă de numere naturale nenule, fără să conteze ordinea termenilor. Ca să nu repetăm aceeași descompunere, termenii se generează în ordine crescătoare (x[k] ≥ x[k - 1]). Ținem cât a rămas din n: un termen e valid dacă nu depășește restul, iar soluția e completă când restul devine 0.

Complexity
proportional to the number of partitions (grows exponentially with n)
Grade
Grade 11 (Clasa a XI-a)

Examples

Example 1

Input

4

Expected output

1+1+1+1
1+1+2
1+3
2+2
4

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

partitiile-unui-numar.cpp
/*
 * Titlu: Partițiile unui număr natural
 * Clasa: 11
 * Capitol: Metoda backtracking
 * Descriere: Afișează toate modurile de a scrie n ca sumă de numere naturale nenule,
 *            fără să conteze ordinea termenilor. Ca să nu repetăm aceeași descompunere,
 *            termenii se generează în ordine crescătoare (x[k] ≥ x[k - 1]). Ținem cât a
 *            rămas din n: un termen e valid dacă nu depășește restul, iar soluția e
 *            completă când restul devine 0.
 * Complexitate: proporțională cu numărul de partiții (crește exponențial cu n)
 *
 * Exemplu
 * Intrare: 4
 * Ieșire:
 * 1+1+1+1
 * 1+1+2
 * 1+3
 * 2+2
 * 4
 */
#include <iostream>
using namespace std;

int n, x[100];

void afiseaza(int lungime)
{
    for (int i = 1; i <= lungime; i++)
    {
        if (i > 1)
        {
            cout << '+';
        }
        cout << x[i];
    }
    cout << '\n';
}

void back(int k, int ramas)
{
    // x[0] = 1, deci primul termen pornește de la 1
    for (int v = x[k - 1]; v <= ramas; v++)
    {
        x[k] = v;
        if (v == ramas)
        {
            afiseaza(k);
        }
        else
        {
            back(k + 1, ramas - v);
        }
    }
}

int main()
{
    cin >> n;
    x[0] = 1;
    back(1, n);
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.