经典问题——输出n对括号的所有组合

Bertha 。 2023-08-17 15:46 121阅读 0赞

## 问题 ##

n对括号有多少种合法的组合，比如两对括号可以有两种：（）（）和（（））

## 思路 ##

问题等价为：在一个字符串中包含两种字符：'('和')'，他们出现的次数都为n，并且任何时候'('出现的次数总是大于或等于')'出现的次数。

解决方案：（递归）

n表示括号对数，l表示已有括号个数，r表示已有右括号个数  
若r = n,则输出结果  
若l < r,不可能  
若l = r,则加上左括号  
若l > r,分类讨论，若l = n,则全部补充右括号；若l < n,可加左括号或加右括号

## 代码 ##

1 #include<cstdio>
     2 #include<iostream>
     3 #include<string>
     4 using namespace std;
     5 
     6 int n;
     7 
     8 void general(int n,int l,int r,int& num,string res)
     9 {
    10     if (r == n)
    11     {
    12         num++;
    13         cout << res << endl;
    14         return;
    15     }
    16     if (l == r)
    17     {
    18         l++;
    19         res = res + '(';
    20         general(n, l, r, num, res);
    21     }
    22     else
    23     {
    24         if (l != n)
    25         {
    26             l++;
    27             res = res + '(';
    28             general(n, l, r, num, res);
    29 
    30             res.pop_back();
    31             l--;
    32             r++;
    33             res = res + ')';
    34             general(n, l, r, num, res);
    35         }
    36         else
    37         {
    38             r++;
    39             res = res + ')';
    40             general(n, l, r, num, res);
    41         }
    42     }
    43     return;
    44 }
    45 
    46 int main()
    47 {
    48     string str;
    49     int num;
    50     while (scanf("%d",&n) == 1)
    51     {
    52         num = 0;
    53         general(n, 0, 0, num, str);
    54         printf("%d\n", num);
    55     }
    56     return 0;
    57 }

参考链接：[https://blog.csdn.net/u014529413/article/details/39119273][https_blog.csdn.net_u014529413_article_details_39119273]

转载于:https://www.cnblogs.com/lfri/p/10294271.html

[https_blog.csdn.net_u014529413_article_details_39119273]: https://blog.csdn.net/u014529413/article/details/39119273