Print all partitions of a given number

Question

The task is to write a C++ recursive function, that receives an integer and prints all of it partitions. (with importance to order)

Examples:

n=1 the only permutation is {1}

n=2 the permutations are {1,1},{2}

n=3 the permutations are {1,1,1},{1,2},{2,1},{3}

n=4 the permutations are {1,1,1,1},{1,1,2},{1,2,1},{1,3},{2,1,1},{2,2},{3,1},{4}

note the importance for order, for example for n=3 both {1,2} and {2,1} are different and valid answers.

Here is my solution which contains a bug that I'm having a hard time to trace:

#include <iostream>
#include <string>
#include <sstream>
#include <stack>
using namespace std;

stringstream g_ss_str("");

void printSums(int n){
    static stack<string> strings;
    if (n==0){
        cout<<g_ss_str.str()<<endl;
        return;
    }
    for (int i=1; i<=n; ++i){
        g_ss_str<<i<<" ";
        strings.push(g_ss_str.str());
        printSums(n-i);
        
        if (!strings.empty()) {
            g_ss_str.str(strings.top());
            strings.pop();
        }
    }
}

The problem starts with n=3, in that case the output I get is:

1 1 1

2 1

3

Instead of:

1 1 1

1 2

2 1

3

Appreciate your help!

those "things" are called partitions in math, not permutations . — user2485710
– user2485710, Commented Nov 29, 2014 at 0:45

Igor Tandetnik · Accepted Answer · 2014-11-29 01:33:49Z

3

You are playing some unnecessarily complicated games with your stringstream and your stack. Try something like this:

void printSumsHelper(int n, const string& prefix) {
    if (n==0){
        cout << prefix << endl;
        return;
    }

    for (int i=1; i<=n; ++i) {
        ostringstream ss;
        ss << prefix << i << ' ';
        printSumsHelper(n - i, ss.str());
    }
}

void printSums(int n){
    printSumsHelper(n, "");
}

answered Nov 29, 2014 at 1:33

Igor Tandetnik

53.1k4 gold badges65 silver badges93 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Print all partitions of a given number

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related