#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to print the contents of the given vector
void printCombination(vector<int> const &out)
{
for (int i: out)
cout << i << " ";
cout << endl;
}
// Recursive function to print all combination of numbers
// from i to n having sum n
void recurse(int i, int n, vector<int> &out)
{
// if sum becomes n, print the combination
if (n == 0)
printCombination(out);
// start from previous element in the combination till n
for (int j = i; j <= n; j++)
{
// proceed only if j not added earlier
if (std::find(out.begin(), out.end(), j) == out.end())
{
// include current element from combination
out.push_back(j);
// recurse with reduced sum
recurse(j, n - j, out);
// backtrack - remove current element from combination
out.pop_back();
}
}
}
// main function
int main()
{
int n = 5;
vector<int> out;
// recurse all combination of numbers from 1 to n having sum n
recurse(1, n, out);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy8gRnVuY3Rpb24gdG8gcHJpbnQgdGhlIGNvbnRlbnRzIG9mIHRoZSBnaXZlbiB2ZWN0b3IKdm9pZCBwcmludENvbWJpbmF0aW9uKHZlY3RvcjxpbnQ+IGNvbnN0ICZvdXQpCnsKICAgIGZvciAoaW50IGk6IG91dCkKICAgICAgICBjb3V0IDw8IGkgPDwgIiAiOwoKICAgIGNvdXQgPDwgZW5kbDsKfQoKLy8gUmVjdXJzaXZlIGZ1bmN0aW9uIHRvIHByaW50IGFsbCBjb21iaW5hdGlvbiBvZiBudW1iZXJzCi8vIGZyb20gaSB0byBuIGhhdmluZyBzdW0gbgp2b2lkIHJlY3Vyc2UoaW50IGksIGludCBuLCB2ZWN0b3I8aW50PiAmb3V0KQp7CiAgICAvLyBpZiBzdW0gYmVjb21lcyBuLCBwcmludCB0aGUgY29tYmluYXRpb24KICAgIGlmIChuID09IDApCiAgICAgICAgcHJpbnRDb21iaW5hdGlvbihvdXQpOwoKICAgIC8vIHN0YXJ0IGZyb20gcHJldmlvdXMgZWxlbWVudCBpbiB0aGUgY29tYmluYXRpb24gdGlsbCBuCiAgICBmb3IgKGludCBqID0gaTsgaiA8PSBuOyBqKyspCiAgICB7CiAgICAgICAgLy8gcHJvY2VlZCBvbmx5IGlmIGogbm90IGFkZGVkIGVhcmxpZXIKICAgICAgICBpZiAoc3RkOjpmaW5kKG91dC5iZWdpbigpLCBvdXQuZW5kKCksIGopID09IG91dC5lbmQoKSkKICAgICAgICB7CiAgICAgICAgICAgIC8vIGluY2x1ZGUgY3VycmVudCBlbGVtZW50IGZyb20gY29tYmluYXRpb24KICAgICAgICAgICAgb3V0LnB1c2hfYmFjayhqKTsKCiAgICAgICAgICAgIC8vIHJlY3Vyc2Ugd2l0aCByZWR1Y2VkIHN1bQogICAgICAgICAgICByZWN1cnNlKGosIG4gLSBqLCBvdXQpOwoKICAgICAgICAgICAgLy8gYmFja3RyYWNrIC0gcmVtb3ZlIGN1cnJlbnQgZWxlbWVudCBmcm9tIGNvbWJpbmF0aW9uCiAgICAgICAgICAgIG91dC5wb3BfYmFjaygpOwogICAgICAgIH0KICAgIH0KfQoKLy8gbWFpbiBmdW5jdGlvbgppbnQgbWFpbigpCnsKICAgIGludCBuID0gNTsKCiAgICB2ZWN0b3I8aW50PiBvdXQ7CgogICAgLy8gcmVjdXJzZSBhbGwgY29tYmluYXRpb24gb2YgbnVtYmVycyBmcm9tIDEgdG8gbiBoYXZpbmcgc3VtIG4KICAgIHJlY3Vyc2UoMSwgbiwgb3V0KTsKCiAgICByZXR1cm4gMDsKfQo=