学步园

对于2对左右括号，其排列方式有：

( ( ) )
( ) ( )
4对括号的排列方式有：
( ( ( ( ) ) ) )
( ( ( ) ( ) ) )
( ( ( ) ) ( ) )
( ( ( ) ) ) ( )
( ( ) ( ( ) ) )
( ( ) ( ) ( ) )
( ( ) ( ) ) ( )
( ( ) ) ( ( ) )
( ( ) ) ( ) ( )
( ) ( ( ( ) ) )
( ) ( ( ) ( ) )
( ) ( ( ) ) ( )
( ) ( ) ( ( ) )
( ) ( ) ( ) ( )

下面给出生成排列的代码：（原文链接：http://blog.csdn.net/realxie/article/details/8036892 ）

#include <iostream>   
#include <vector>   
using namespace std;  
  
//Print the legal combination   
void PrintBrackets(const vector<char> & brackets)  
{  
    for (vector<char>::const_iterator it = brackets.begin(); it != brackets.end(); ++it)  
        cout << *it <<" ";  
    cout <<endl;  
}  
  
// bracketsNum: the sum of left bracket and right bracket   
void MatchBrackets(int bracketsNum, vector<char> & brackets)  
{  
    int left (0), right(0);  
    for (vector<char>::iterator it = brackets.begin(); it != brackets.end(); ++it)  
    {  
        if ('(' == *it) left ++;  
        else right ++;  
    }  
    // The num of left bracket should not be less than the number of right bracket at any position   
    if (right > left) return;  
      
    if (left == right && left + right == bracketsNum)  
    {  
        PrintBrackets(brackets);  
        return ;  
    }  
      
    if (left + right >= bracketsNum)  
    {  
        return ;  
    }  
      
    // The number of left bracket equal to the number of right bracket,   
    // so we can only append the left bracket '(' now.   
    if (left == right)  
    {  
        brackets.push_back('(');  
        MatchBrackets(bracketsNum, brackets);  
        brackets.pop_back();  
    }  
    // The number of the left bracket equal to bracketsNum/2   
    // no need to append '('.   
    else if (bracketsNum - left == left)  
    {  
        brackets.push_back(')');  
        MatchBrackets(bracketsNum, brackets);  
        brackets.pop_back();  
    }  
    // It`s legal to append '(' and ')'   
    else  
    {  
        brackets.push_back('(');  
        MatchBrackets(bracketsNum, brackets);  
        brackets.pop_back();  
          
        brackets.push_back(')');  
        MatchBrackets(bracketsNum, brackets);  
        brackets.pop_back();  
    }  
}  
  
int main()  
{  
    int braNum;  
    while (cin>> braNum && braNum)  
    {  
        vector<char> brackets;  
        MatchBrackets(braNum, brackets);  
    }  
    return 0;  
}