Generating integer partitions using backtracing & recursion

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.



Program for generating all partitions of an integer

class Partition:

    result = []

    def AllPartitions (self, parts, whole):

        print("\nWhole : " + str(whole))
        print("Parts : " + " ".join(str(parts)))
        print("\n")

        # Generate all the valid partitions using parts (each part can be taken multiple times)
        # to form the whole
        self.Generate(parts, whole, len(parts))
        self.result.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.
    
    def Generate (self, parts, whole, sz):

        if (whole == 0) : 
           for num in self.result :
               print(num, end=" ")
           print("\n")
           return
        elif (sz <= 0 or whole < 0): 
           return

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

        # Sum found with last element excluded
        # Remove the last element that was added to the list earlier.
        self.result.pop()
        self.Generate(parts, whole, sz-1)

def main():

    p = Partition()

    whole = 8 
    parts = [ 1, 2, 3, 4, 5, 6, 7, 8 ] 
    p.AllPartitions(parts, whole)

    parts.clear()

    whole = 16
    parts = [ 1, 2, 4 ] 
    p.AllPartitions(parts, whole)

if __name__ == "__main__":
    main()

Output

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
#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

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 
import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

class Partition {

    private List<Integer> result;

    Partition() {
        result = new ArrayList<Integer>();
    }

    public void AllPartitions (List<Integer> parts, int whole) {

        System.out.println("\nWhole : " + whole);
        System.out.print("Parts : ");
        for(Integer i : parts)
            System.out.print(i + " ");
        System.out.println();

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

        result.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.
    */
    public void Generate (List<Integer> parts, int whole, int sz) {

        if (whole == 0) {
           for(Integer i : result)
              System.out.print(i + " ");
           System.out.println();
           return;
        } else if (sz <= 0 || whole < 0) {
           return;
        }

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

        // Sum found with last element excluded
        // Remove the last element that was added to the list earlier.
        result.remove(result.size()-1);
        Generate(parts, whole, sz-1);
    }

    public static void main (String args[]) {

        Partition p = new Partition();

        int whole = 8;
        List<Integer> parts = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8);
        p.AllPartitions(parts, whole);

        whole = 16;
        List<Integer> parts1 = Arrays.asList(1, 2, 4);
        p.AllPartitions(parts1, whole);
    }
};

Output

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