Generating integer partitions using backtracing & recursion

Generating all partitions of an integer.

Partitions of an integer are the different ways of writing the integer as a sum of parts.
The parts can be the set of all integers or some restricted set.
Note: This set does not contain 0 as then there would be infinite partitions.

Example: The partitions of 5, when the parts are 1, 2, 3, 4, 5 are :

  • 5
  • 1 + 4
  • 2 + 3
  • 1 + 1 + 3
  • 1 + 2 + 2
  • 1 + 1 + 1 + 2
  • 1 + 1 + 1 + 1 + 1

Thus there are in total 7 partitions of 5, given this set of parts.


Python

Python3 program for generating all the partitions of an integer using backtracking & recursion.


Java

Java program for generating all the partitions of an integer using backtracking & recursion.


C++ program for generating all the partitions of an integer using backtracking & recursion.

#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();
    }

    /* Recursive method to generate all possible partitions.
       This method stores the possible combinations in 'result' while continuously
       decreasing the value of the whole. If the whole is reduced to 0, result will have
       a valid partition.
    */
    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);
    }
};

int main() {

    Partition p;

    int whole = 8;
    vector<int> parts = { 1, 2, 3, 4, 5, 6, 7, 8 };
    p.AllPartitions(parts, whole);

    whole = 16; 
    vector<int> parts1 = { 1, 2 , 4 };
    p.AllPartitions(parts1, whole);
    return 0;
}

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 (c) 2020-2021, Algotree.org.
All rights reserved.