Generating all partitions of a given number: A partition of a positive integer number "n" is a way of writing "n" as a sum of positive integers.

int_partition.cpp

#include <iostream>

// Output a partition:
void output_partition(const int n, const int *x, const int how_many_partitions)
{
    std::cout << "Partition(" << how_many_partitions << ")" << " = ";
    for (int i = 1; i <= n; i++)
    {
        // Can't show negative numbers:
        if (x[i] > 0)
        {
            if (i == n)
                std::cout << x[i];
            else
                std::cout << x[i] << " + ";
        }
    }
    std::cout << std::endl;
}

// This is the function which generates the partitions of a given number "n".
void generate_partitions(int *x, const int n)
{
    int k, s = 0; // s represents the sum of already-generated components
    // Initialize the solution vector's elements with -1
    int how_many_partitions = 0;
    for (k = 1; k < n; k++)
        x[k] = -1;
    k = 1;
    while (k > 0)
    {
        // Generated a solution, let's output it then:
        if (k == n)
        {
            how_many_partitions++; // Increase the number of generated partitions
            x[n] = n - s;
            output_partition(n, x, how_many_partitions);
            k--;
            s = s - x[k];
        }
        else
        {
            // Check for another solution:
            if (((n - k + 1) * (x[k] + 1)) <= n - s)
            {
                x[k]++;
                if (x[k] >= x[k - 1])
                {
                    s = s + x[k];
                    k++;
                }
            }
            else
            {
                                // Didn't find any solutions, reset x[k] to -1
                x[k] = -1;
                k--;
                s = s - x[k];
            }
        }
    }
}

// Test:
int main()
{
    int number;
    std::cout << "n = ";
    std::cin >> number;
    int *x = new int[number + 1];
    x[0] = 0;
    std::cout << "Partitions of " << number << ":\n\n";
    generate_partitions(x, number);
    delete [] x;
    std::cin.ignore();
    std::cin.get();
    return 0;
}