Generating integer partitions using recursion

Generating all partitions of an integer


C++ : Generating all the partitions of an integer implemented using C++11

#include<iostream>
#include<set>
#include<vector>
using namespace std;

class Partition {

public:
    vector<int> result;
    vector<vector<int>> allparts;

    void AllPartitions(vector<int>& parts, int whole) {

        cout << "Whole : " << whole << endl;
        cout << "Parts : ";
        for(const auto& i : parts)
            cout << i << " ";
        cout << endl;

        // Generate all the valid partitions using parts (each part can be taken multiple times)
        // to form the whole
        Generate(parts, whole, parts.size());

        for (const auto& p : allparts) {
            for (const auto& i : p)
                cout << i << " ";
            cout << endl;
        }
        cout << endl;
        result.clear();
        allparts.clear();
    }

    void Generate(vector<int>& parts, int whole, int sz) {

        if (whole == 0) {
           allparts.push_back(result);
           return;
        } else if (sz <= 0 or whole < 0) {
           return;
        }

        // Sum found with the last element included
        result.push_back(parts[sz-1]);
        Generate(parts, whole-parts[sz-1], sz);

        // Sum found with last element excluded
        result.pop_back();
        Generate(parts, whole, sz-1);
    }
};

Output of generating all partitions of an integer (whole) using valid parts.

Whole : 8
Parts : 1 2 3 4 5 6 7 8 
8 
7 1 
6 2 
6 1 1 
5 3 
5 2 1 
5 1 1 1 
4 4 
4 3 1 
4 2 2 
4 2 1 1 
4 1 1 1 1 
3 3 2 
3 3 1 1 
3 2 2 1 
3 2 1 1 1 
3 1 1 1 1 1 
2 2 2 2 
2 2 2 1 1 
2 2 1 1 1 1 
2 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 

Whole : 16
Parts : 1 2 4 
4 4 4 4 
4 4 4 2 2 
4 4 4 2 1 1 
4 4 4 1 1 1 1 
4 4 2 2 2 2 
4 4 2 2 2 1 1 
4 4 2 2 1 1 1 1 
4 4 2 1 1 1 1 1 1 
4 4 1 1 1 1 1 1 1 1 
4 2 2 2 2 2 2 
4 2 2 2 2 2 1 1 
4 2 2 2 2 1 1 1 1 
4 2 2 2 1 1 1 1 1 1 
4 2 2 1 1 1 1 1 1 1 1 
4 2 1 1 1 1 1 1 1 1 1 1 
4 1 1 1 1 1 1 1 1 1 1 1 1 
2 2 2 2 2 2 2 2 
2 2 2 2 2 2 2 1 1 
2 2 2 2 2 2 1 1 1 1 
2 2 2 2 2 1 1 1 1 1 1 
2 2 2 2 1 1 1 1 1 1 1 1 
2 2 2 1 1 1 1 1 1 1 1 1 1 
2 2 1 1 1 1 1 1 1 1 1 1 1 1 
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 

Copyright © 2020, Algotree.org.
All rights reserved.