Why is my output for Balanced Bracket Problem using Recursion wrong

Question

So I wrote some recursive code for printing balanced brackets when number of bracket pairs (noOfPairs) are given as the input. But my answers are wrong.

For example: On inputting n = 2, the two types of brackets would be (()) or ()() but my program is outputting (()) and (()( which is wrong. Kindly help!

// Generate Brackets Strings Problem
// Using Recursion
// Given a number N, generate BALANCED BRACKETS using n pairs of Round Brackets

#include<iostream>
#include<cstring>

using namespace std;

// recursive function
void generateBrackets(string output, int noOfPairs, int open, int close) {   // open = open brac ; close = close brac
    // base case
    if (output.length() == 2 * noOfPairs) {
        cout << output << endl;
        return;
    }
    // adding brackets (recursive)
    // 2 ways in the middle of the string
    if (open < noOfPairs) {
        output.push_back('(');
        generateBrackets(output, noOfPairs, open + 1, close);
    }
    if (close < open) {
        output.push_back(')');
        generateBrackets(output, noOfPairs, open, close + 1);
    }
    return;
}

int main() {
    // input
    int n;
    cout << "Enter the number of pairs of round brackets" << endl;
    cin >> n;

    // make an output string
    string output;

    generateBrackets(output, n, 0, 0);

    return 0;
}

Answer 1

After the first recursive call to generateBrackets, you need to pop the '(' that you had just pushed, because otherwise it will interfere with the next call where you add a close bracket.