为什么我的 Balanced Bracket Problem using Recursion 输出错误

Question

因此，我编写了一些递归代码，用于在括号对数 (noOfPairs) 作为输入给出时打印平衡括号。但是我的答案是错误的。

例如：在输入 n = 2 时，两种类型的括号将是 (()) 或 ()() 但我的程序输出的是 (()) 和 (()( 这是错误的。请帮助!

// 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

在对 generateBrackets 的第一次递归调用后，您需要弹出刚刚推送的 '('，否则它会干扰您添加右括号的下一次调用。

Answer 2

#include<iostream>
using namespace std;
void parenthesis(int open, int close, string brak)
{
   if (open == 0 && close == 0)
      cout<<brak;
   if (open>close)
      return;
   if (open > 0)
      parenthesis(open-1, close,brak + "(");
   if (close > 0)
      parenthesis(open, close - 1,brak + ")");
}
void printPar(int n)
{
   parenthesis(n,n,"\n");
}
int main()
{
   int n=1;
   printPar(n);
   return  0;

}

为什么我的 Balanced Bracket Problem using Recursion 输出错误

Why is my output for Balanced Bracket Problem using Recursion wrong

c++

string

algorithm

recursion

backtracking