CODEWITHSUNDEEP
c++algorithmsum
Yan4321
Yan4321

Reputation: 339

Print all partitions of a given number

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

2 1

3

Instead of:

1 1 1

1 2

2 1

3

Appreciate your help!

Upvotes: 0

Views: 722

Answers (1)

Igor Tandetnik
Igor Tandetnik

Reputation: 52471

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, "");
}

Upvotes: 3

Related Questions