# Generate all unique partitions of an integer

• Difficulty Level : Hard
• Last Updated : 26 Nov, 2022

Given a positive integer n, generate all possible unique ways to represent n as sum of positive integers.

Examples:

```  Input: n = 2
Output:
2
1 1

Input: n = 3
Output:
3
2 1
1 1 1
Note: 2+1 and 1+2 are considered as duplicates.

Input: n = 4
Output:
4
3 1
2 2
2 1 1
1 1 1 1 ```
Recommended Practice

Solution: We print all partition in sorted order and numbers within a partition are also printed in sorted order (as shown in the above examples). The idea is to get the next partition using the values in the current partition. We store every partition in an array p[]. We initialize p[] as n where n is the input number. In every iteration. we first print p[] and then update p[] to store the next partition. So the main problem is to get the next partition from a given partition.

Steps to get next partition from current partition:
We are given current partition in p[] and its size. We need to update p[] to store next partition. Values in p[] must be sorted in non-increasing order.

1. Find the rightmost non-one value in p[] and store the count of 1’s encountered before a non-one value in a variable rem_val (It indicates sum of values on right side to be updated). Let the index of non-one value be k.
2. Decrease the value of p[k] by 1 and increase rem_val by 1. Now there may be two cases:
• a) If p[k] is more than or equal to rem_val. This is a simple case (we have the sorted order in new partition). Put rem_val at p[k+1] and p[0…k+1] is our new partition.
• b) Else (This is a interesting case, take initial p[] as {3, 1, 1, 1}, p[k] is decreased from 3 to 2, rem_val is increased from 3 to 4, divide rem_val in different values of size p[k] and copy these values at different positions after p[k], so the next partition should be {2, 2, 2}).
3. Copy p[k] to next position, increment k and reduce count by p[k] while p[k] is less than rem_val. Finally, put rem_val at p[k+1] and p[0…k+1] is our new partition. This step is like dividing rem_val in terms of p[k] (4 is divided in 2’s).

Following is the implementation of above algorithm:

## C++

 `// CPP program to generate all unique``// partitions of an integer``#include``using` `namespace` `std;` `// A utility function to print an array p[] of size 'n'``void` `printArray(``int` `p[], ``int` `n)``{``    ``for` `(``int` `i = 0; i < n; i++)``    ``cout << p[i] << ``" "``;``    ``cout << endl;``}` `void` `printAllUniqueParts(``int` `n)``{``    ``int` `p[n]; ``// An array to store a partition``    ``int` `k = 0; ``// Index of last element in a partition``    ``p[k] = n; ``// Initialize first partition as number itself` `    ``// This loop first prints current partition then generates next``    ``// partition. The loop stops when the current partition has all 1s``    ``while` `(``true``)``    ``{``        ``// print current partition``        ``printArray(p, k+1);` `        ``// Generate next partition` `        ``// Find the rightmost non-one value in p[]. Also, update the``        ``// rem_val so that we know how much value can be accommodated``        ``int` `rem_val = 0;``        ``while` `(k >= 0 && p[k] == 1)``        ``{``            ``rem_val += p[k];``            ``k--;``        ``}` `        ``// if k < 0, all the values are 1 so there are no more partitions``        ``if` `(k < 0) ``return``;` `        ``// Decrease the p[k] found above and adjust the rem_val``        ``p[k]--;``        ``rem_val++;`  `        ``// If rem_val is more, then the sorted order is violated. Divide``        ``// rem_val in different values of size p[k] and copy these values at``        ``// different positions after p[k]``        ``while` `(rem_val > p[k])``        ``{``            ``p[k+1] = p[k];``            ``rem_val = rem_val - p[k];``            ``k++;``        ``}` `        ``// Copy rem_val to next position and increment position``        ``p[k+1] = rem_val;``        ``k++;``    ``}``}` `// Driver program to test above functions``int` `main()``{``    ``cout << ``"All Unique Partitions of 2 \n"``;``    ``printAllUniqueParts(2);` `    ``cout << ``"\nAll Unique Partitions of 3 \n"``;``    ``printAllUniqueParts(3);` `    ``cout << ``"\nAll Unique Partitions of 4 \n"``;``    ``printAllUniqueParts(4);` `    ``return` `0;``}`

## Java

 `// Java program to generate all unique``// partitions of an integer``import` `java.io.*;` `class` `GFG``{``    ``// Function to print an array p[] of size n``    ``static` `void` `printArray(``int` `p[], ``int` `n)``    ``{``        ``for` `(``int` `i = ``0``; i < n; i++)``            ``System.out.print(p[i]+``" "``);``        ``System.out.println();``    ``}``    ` `    ``// Function to generate all unique partitions of an integer``    ``static` `void` `printAllUniqueParts(``int` `n)``    ``{``        ``int``[] p = ``new` `int``[n]; ``// An array to store a partition``        ``int` `k = ``0``;  ``// Index of last element in a partition``        ``p[k] = n;  ``// Initialize first partition as number itself`` ` `        ``// This loop first prints current partition then generates next``        ``// partition. The loop stops when the current partition has all 1s``        ``while` `(``true``)``        ``{``            ``// print current partition``            ``printArray(p, k+``1``);`` ` `            ``// Generate next partition`` ` `            ``// Find the rightmost non-one value in p[]. Also, update the``            ``// rem_val so that we know how much value can be accommodated``            ``int` `rem_val = ``0``;``            ``while` `(k >= ``0` `&& p[k] == ``1``)``            ``{``                ``rem_val += p[k];``                ``k--;``            ``}`` ` `            ``// if k < 0, all the values are 1 so there are no more partitions``            ``if` `(k < ``0``)  ``return``;`` ` `            ``// Decrease the p[k] found above and adjust the rem_val``            ``p[k]--;``            ``rem_val++;`` ` ` ` `            ``// If rem_val is more, then the sorted order is violated.  Divide``            ``// rem_val in different values of size p[k] and copy these values at``            ``// different positions after p[k]``            ``while` `(rem_val > p[k])``            ``{``                ``p[k+``1``] = p[k];``                ``rem_val = rem_val - p[k];``                ``k++;``            ``}`` ` `            ``// Copy rem_val to next position and increment position``            ``p[k+``1``] = rem_val;``            ``k++;``        ``}``    ``}``    ` `    ``// Driver program``    ``public` `static` `void` `main (String[] args)``    ``{``        ``System.out.println(``"All Unique Partitions of 2"``);``        ``printAllUniqueParts(``2``);``        ` `        ``System.out.println(``"All Unique Partitions of 3"``);``        ``printAllUniqueParts(``3``);``        ` `        ``System.out.println(``"All Unique Partitions of 4"``);``        ``printAllUniqueParts(``4``);``    ``}``}` `// Contributed by Pramod Kumar`

## Python3

 `# A utility function to print an``# array p[] of size 'n'``def` `printArray(p, n):``    ``for` `i ``in` `range``(``0``, n):``        ``print``(p[i], end ``=` `" "``)``    ``print``()` `def` `printAllUniqueParts(n):``    ``p ``=` `[``0``] ``*` `n     ``# An array to store a partition``    ``k ``=` `0`         `# Index of last element in a partition``    ``p[k] ``=` `n     ``# Initialize first partition``                 ``# as number itself` `    ``# This loop first prints current partition,``    ``# then generates next partition.The loop``    ``# stops when the current partition has all 1s``    ``while` `True``:``        ` `            ``# print current partition``            ``printArray(p, k ``+` `1``)` `            ``# Generate next partition` `            ``# Find the rightmost non-one value in p[].``            ``# Also, update the rem_val so that we know``            ``# how much value can be accommodated``            ``rem_val ``=` `0``            ``while` `k >``=` `0` `and` `p[k] ``=``=` `1``:``                ``rem_val ``+``=` `p[k]``                ``k ``-``=` `1` `            ``# if k < 0, all the values are 1 so``            ``# there are no more partitions``            ``if` `k < ``0``:``                ``print``()``                ``return` `            ``# Decrease the p[k] found above``            ``# and adjust the rem_val``            ``p[k] ``-``=` `1``            ``rem_val ``+``=` `1` `            ``# If rem_val is more, then the sorted``            ``# order is violated. Divide rem_val in``            ``# different values of size p[k] and copy``            ``# these values at different positions after p[k]``            ``while` `rem_val > p[k]:``                ``p[k ``+` `1``] ``=` `p[k]``                ``rem_val ``=` `rem_val ``-` `p[k]``                ``k ``+``=` `1` `            ``# Copy rem_val to next position``            ``# and increment position``            ``p[k ``+` `1``] ``=` `rem_val``            ``k ``+``=` `1` `# Driver Code``print``(``'All Unique Partitions of 2'``)``printAllUniqueParts(``2``)` `print``(``'All Unique Partitions of 3'``)``printAllUniqueParts(``3``)` `print``(``'All Unique Partitions of 4'``)``printAllUniqueParts(``4``)` `# This code is contributed``# by JoshuaWorthington`

## C#

 `// C# program to generate all unique``// partitions of an integer``using` `System;` `class` `GFG {``    ` `    ``// Function to print an array p[]``    ``// of size n``    ``static` `void` `printArray(``int` `[]p, ``int` `n)``    ``{``        ``for` `(``int` `i = 0; i < n; i++)``            ``Console.Write(p[i]+``" "``);``            ` `        ``Console.WriteLine();``    ``}``    ` `    ``// Function to generate all unique``    ``// partitions of an integer``    ``static` `void` `printAllUniqueParts(``int` `n)``    ``{``        ` `        ``// An array to store a partition``        ``int``[] p = ``new` `int``[n];``        ` `        ``// Index of last element in a``        ``// partition``        ``int` `k = 0;``        ` `        ``// Initialize first partition as``        ``// number itself``        ``p[k] = n;` `        ``// This loop first prints current``        ``// partition, then generates next``        ``// partition. The loop stops when``        ``// the current partition has all 1s``        ``while` `(``true``)``        ``{``            ` `            ``// print current partition``            ``printArray(p, k+1);` `            ``// Generate next partition` `            ``// Find the rightmost non-one``            ``// value in p[]. Also, update``            ``// the rem_val so that we know``            ``// how much value can be``            ``// accommodated``            ``int` `rem_val = 0;``            ` `            ``while` `(k >= 0 && p[k] == 1)``            ``{``                ``rem_val += p[k];``                ``k--;``            ``}` `            ``// if k < 0, all the values are 1 so``            ``// there are no more partitions``            ``if` `(k < 0)``                ``return``;` `            ``// Decrease the p[k] found above``            ``// and adjust the rem_val``            ``p[k]--;``            ``rem_val++;`  `            ``// If rem_val is more, then the sorted``            ``// order is violated. Divide rem_val in``            ``// different values of size p[k] and copy``            ``// these values at different positions``            ``// after p[k]``            ``while` `(rem_val > p[k])``            ``{``                ``p[k+1] = p[k];``                ``rem_val = rem_val - p[k];``                ``k++;``            ``}` `            ``// Copy rem_val to next position and``            ``// increment position``            ``p[k+1] = rem_val;``            ``k++;``        ``}``    ``}``    ` `    ``// Driver program``    ``public` `static` `void` `Main ()``    ``{``        ``Console.WriteLine(``"All Unique Partitions of 2"``);``        ``printAllUniqueParts(2);``        ` `        ``Console.WriteLine(``"All Unique Partitions of 3"``);``        ``printAllUniqueParts(3);``        ` `        ``Console.WriteLine(``"All Unique Partitions of 4"``);``        ``printAllUniqueParts(4);``    ``}``}` `// This code is contributed by Sam007.`

## PHP

 `= 0 && ``\$p``[``\$k``] == 1)``        ``{``            ``\$rem_val` `+= ``\$p``[``\$k``];``            ``\$k``--;``        ``}` `        ``// if k < 0, all the values``        ``// are 1 so there are no``        ``// more partitions``        ``if` `(``\$k` `< 0) ``return``;` `        ``// Decrease the p[k] found``        ``// above and adjust the``        ``// rem_val``        ``\$p``[``\$k``]--;``        ``\$rem_val``++;`  `        ``// If rem_val is more, then``        ``// the sorted order is violated.``        ``// Divide rem_val in different``        ``// values of size p[k] and copy``        ``// these values at different``        ``// positions after p[k]``        ``while` `(``\$rem_val` `> ``\$p``[``\$k``])``        ``{``            ``\$p``[``\$k` `+ 1] = ``\$p``[``\$k``];``            ``\$rem_val` `= ``\$rem_val` `- ``\$p``[``\$k``];``            ``\$k``++;``        ``}` `        ``// Copy rem_val to next``        ``// position and increment``        ``// position``        ``\$p``[``\$k` `+ 1] = ``\$rem_val``;``        ``\$k``++;``    ``}``}` `// Driver Code``echo` `"All Unique Partitions of 2 \n"``;``printAllUniqueParts(2);` `echo` `"\nAll Unique Partitions of 3 \n"``;``printAllUniqueParts(3);` `echo` `"\nAll Unique Partitions of 4 \n"``;``printAllUniqueParts(4);` `// This code is contributed``// by akt_mit``?>`

## Javascript

 ``

Output:

```All Unique Partitions of 2
2
1 1

All Unique Partitions of 3
3
2 1
1 1 1

All Unique Partitions of 4
3 1
2 2
2 1 1
1 1 1 1```

Time Complexity: O(n * k)

Auxiliary Space: O(n)

Recursive Approach:

The idea behind this approach is  to find maximum sum by taking and not-taking concept, if we are taking an element it must by at least at a difference of two from the previous taken elements index.

Below are the steps :

1. Take a vector and store elements from 1 to n
2. create solve function to find set of elements having sum=n
3. we have two base cases:
4. if(sum==n) store the vector in a vector<vector<int>> and return
5. if(index<0) return directly
6. recursively traverse a vector by not taking any element initially
7. above recursive function returns a call at index =0
8. next we take element in a  vector and then find recursively its 2nd neighbour
9. then we pop element that was last pushed.

Here is the complete implementation  of the approach:

## C++

 `// c++ code``#include ``using` `namespace` `std;``class` `Solution {``public``:``    ``vector<``int``> temp;``    ``void` `solve(vector<``int``> a, vector >& v,``               ``int` `idx, ``int` `sum, ``int` `n)``    ``{``        ``// first base case if sum=n we can store vector in a``        ``// vector``        ``if` `(sum == n) {``            ``v.push_back(temp);``            ``return``;``        ``}``        ``// if idx < 0 return``        ``if` `(idx < 0) {``            ``return``;``        ``}``        ``// not take condition``        ``solve(a, v, idx - 1, sum, n);``        ``if` `(sum < n) {``            ``temp.push_back(a[idx]);``            ``// this is main condition where we can take one``            ``// element many times``            ``solve(a, v, idx, sum + a[idx], n);``            ``temp.pop_back();``        ``}``    ``}``    ``vector > UniquePartitions(``int` `n)``    ``{``        ``vector<``int``> a;``        ``// vector to store elements from 1 to n``        ``for` `(``int` `i = 1; i <= n; i++) {``            ``a.push_back(i);``        ``}``        ``vector > v;``        ``// call solve to get answer``        ``solve(a, v, n - 1, 0, n);``        ``reverse(v.begin(), v.end());``        ``return` `v;``    ``}``};``int` `main()``{``    ``Solution ob;``    ``vector > ans = ob.UniquePartitions(4);``    ``cout << ``"for 4\n"``;``    ``for` `(``auto` `i : ans) {``        ``for` `(``auto` `j : i) {``            ``cout << j << ``" "``;``        ``}``        ``cout << ``"\n"``;``    ``}``    ``vector > a = ob.UniquePartitions(3);``    ``cout << ``"\n"``;``    ``cout << ``"for 3\n"``;``    ``for` `(``auto` `i : a) {``        ``for` `(``auto` `j : i) {``            ``cout << j << ``" "``;``        ``}``        ``cout << ``"\n"``;``    ``}``    ``return` `0;``}`

Output

```for 4
4
3 1
2 2
2 1 1
1 1 1 1

for 3
3
2 1
1 1 1 ```
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}