打印所有括号匹配排列方式

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

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

下面给出生成排列的代码：

#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 == right)
{
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;
}