Grade 11 · Dynamic programmingCitește în română

Number of partitions of a number

Original: Numărul partițiilor unui număr

O(n²)C++1741 lines2 examples

The idea

In how many ways can n be written as a sum of non-zero natural numbers, where the order of the terms does not matter? (4 = 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1, so 5.) Backtracking would enumerate them all; here we only count them. We introduce the possible terms t = 1, 2, ..., n one at a time. nr[s] is the number of ways to write s using only the terms introduced so far; when we add the term t, nr[s] += nr[s - t] (for increasing s, so that t can be used several times). Initially nr[0] = 1.

Original description (Romanian)

În câte moduri se poate scrie n ca sumă de numere naturale nenule, fără să conteze ordinea termenilor? (4 = 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1, deci 5.) Backtracking-ul le-ar enumera pe toate; aici doar le numărăm. Introducem pe rând termenii posibili t = 1, 2, ..., n. nr[s] este numărul de moduri de a scrie s folosind doar termenii introduși până acum; când adăugăm termenul t, nr[s] += nr[s - t] (pentru s crescător, ca t să poată fi folosit de mai multe ori). Inițial nr[0] = 1.

Complexity
O(n²) timp, O(n) memorie
Grade
Grade 11 (Clasa a XI-a)

Examples

Example 1

Input

5

Expected output

7
Example 2

Input

10

Expected output

42

The code

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

numarul-partitiilor.cpp
/*
 * Titlu: Numărul partițiilor unui număr
 * Clasa: 11
 * Capitol: Programare dinamică
 * Descriere: În câte moduri se poate scrie n ca sumă de numere naturale nenule, fără să
 *            conteze ordinea termenilor? (4 = 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1, deci 5.)
 *            Backtracking-ul le-ar enumera pe toate; aici doar le numărăm. Introducem
 *            pe rând termenii posibili t = 1, 2, ..., n. nr[s] este numărul de moduri de a
 *            scrie s folosind doar termenii introduși până acum; când adăugăm termenul t,
 *            nr[s] += nr[s - t] (pentru s crescător, ca t să poată fi folosit de mai multe
 *            ori). Inițial nr[0] = 1.
 * Complexitate: O(n²) timp, O(n) memorie
 *
 * Exemplu
 * Intrare: 5
 * Ieșire: 7
 *
 * Exemplu
 * Intrare: 10
 * Ieșire: 42
 */
#include <iostream>
using namespace std;

int main()
{
    int n;
    long long nr[205] = {0};
    cin >> n;
    nr[0] = 1;
    for (int t = 1; t <= n; t++)
    {
        for (int s = t; s <= n; s++)
        {
            nr[s] += nr[s - t];
        }
    }
    cout << nr[n] << '\n';
    return 0;
}

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