 |
| Print all possible unique ways to represent n as a sum of positive integers. |
Given a positive integer n, generate all possible unique ways to represent n as a sum of positive integers. The output should be printed in lexicographically decreasing order partitions. For example, if the given number is 52, then 52 itself should be printed first, then 51 1, then 50 2, ... and at the end partition with all 1s.
Note: 2+1 and 1+2 are considered as duplicates.
Print all possible unique ways to represent n as a sum of positive integers.
Example:
Input
2
3
4
Output
3 2 1 1 1 1
4 3 1 2 2 2 1 1 1 1 1 1
For n=4
4
3 1
2 2
2 1 1
1 1 1 1
These 5 possible ways are there so that we can get the sum 4.
#include <iostream>
using namespace std;
void printp(int a[], int n) {
for (int i = 0; i < n; ++i)
cout << a[i] << " ";
}
void solve(int n) {
int p[n];
int k = 0;
p[k] = n;
while (k < n) {
printp(p, k + 1);
int rem_val = 0;
while (k >= 0 && p[k] == 1) {
rem_val += p[k];
k--;
}
if (k < 0)
return;
p[k]--;
++rem_val;
while (rem_val > p[k]) {
p[k + 1] = p[k];
rem_val = rem_val - p[k];
++k;
}
p[k + 1] = rem_val;
++k;
}
}
int main() {
//code
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
solve(n);
cout << endl;
}
return 0;
}
