Every partition of a number using recursion

While doing some backtracking exercises, got stuck here:

Write a recursive algorithm that generates all partitions of a given n numbers. Of the partitions that differ only in the order of the members, we need to list only one, the last from a lexicographic point of view. Write the solutions lexicographically in ascending order. 1 <= n <= 100

n = 5 would be:

I searched over the web for solutions and found this, but it's not quite right and I don't know how to perfect it. First of all it's not in lexicographical order, and doesn't include the actual number.

So for 5 it outputs:

Here is my code, where I tried to correct it, it's better, but still not exactly the way the example is..

#include <iostream>
#include <vector>
using namespace std;

void print(const vector<vector<int>>& output)
{
  for(int i = 0; i < output.size(); ++i){
    for(int j = output[i].size()-1; j >= 0; --j){
      cout << output[i][j] << " "; 
    }
    cout << endl;
  }
}

void iteration(int n, int current_sum, int start, vector<vector<int>>& output, vector<int>& result)
{
    if (n == current_sum) {
        output.push_back(result);
    }

    for (int i = start; i < n; i++) {
        int temp = current_sum + i;
        if (temp <= n) {
            result.push_back(i);
            iteration(n, temp, i, output, result);
            result.pop_back();
        }
        else {
            return ;
        }
    }
}

void decompose(int n) 
{
    vector<vector<int>> output;
    vector<int> result;

    iteration(n, 0, 1, output, result);

    print(output);
    cout << n << endl;

    return ;
}

int main() 
{
    int n = 5;
    decompose(n);

    return 0;
}

So, now the output is:

So, the 2 2 1 and 3 2 is in the wrong place.. And the bigger the "n" number is, the bigger the mess..

Can someone help?

Solution

When you get more practice programming, you'll learn how to keep things simple:

#include <iostream>
#include <vector>

void decompose(int n, std::vector<int> prefix = {}) {
  if (n == 0) {
    for (int a : prefix) { std::cout << a << ' '; }
    std::cout << std::endl;
  }
  else {
    int max = prefix.size() ? std::min(prefix.back(), n) : n;
    prefix.push_back(1);
    for (int i = 1; i <= max; i++) {
      prefix.back() = i;
      decompose(n - i, prefix);
    }
  }
}

int main() {
  decompose(5);
}