抓住小可耐一枚# gardening - 拈花惹草
c*e
1 楼
/*
How can we generate all possibilities on braces ?
N value has given to us and we have to generate all possibilities.
**Examples:**
1) if N == 1, then only one possibility () .
2) if N==2, then possibilities are (()), ()()
3) if N==3, then possibilities are ((())), (())(),()()(), ()(()) ...
Note: left and right braces should match. I mean )( is INVALID for the N==1
How can we solve this problem by using recurrence approach ?
*/
#include
using namespace std;
void PrintStack(deque& s)
{
for(deque::iterator iter = s.begin();iter!=s.end();iter++)
{
cout<}
cout<
void EnumerateBracePairHelp(deque& s, int nCurrLeftBraceNum, int
nMaxPairNum)
{
if(s.size() >= 2*nMaxPairNum)
{
PrintStack(s);
return;
}
// -- check whether we can put a '('
if(nCurrLeftBraceNum < nMaxPairNum)
{
s.push_back('(');
EnumerateBracePairHelp(s, nCurrLeftBraceNum +1, nMaxPairNum);
s.pop_back();
}
// -- check whether we can put a ')'
if( s.size() - nCurrLeftBraceNum < nCurrLeftBraceNum )
{
s.push_back(')');
EnumerateBracePairHelp(s, nCurrLeftBraceNum, nMaxPairNum);
s.pop_back();
}
}
void EnumerateBracePair(int k)
{
if(k<=0)
return;
deque s;
EnumerateBracePairHelp(s,0,k);
}
int main()
{
EnumerateBracePair(5);
return 0;
}
How can we generate all possibilities on braces ?
N value has given to us and we have to generate all possibilities.
**Examples:**
1) if N == 1, then only one possibility () .
2) if N==2, then possibilities are (()), ()()
3) if N==3, then possibilities are ((())), (())(),()()(), ()(()) ...
Note: left and right braces should match. I mean )( is INVALID for the N==1
How can we solve this problem by using recurrence approach ?
*/
#include
using namespace std;
void PrintStack(deque
{
for(deque
{
cout<}
cout<
void EnumerateBracePairHelp(deque
nMaxPairNum)
{
if(s.size() >= 2*nMaxPairNum)
{
PrintStack(s);
return;
}
// -- check whether we can put a '('
if(nCurrLeftBraceNum < nMaxPairNum)
{
s.push_back('(');
EnumerateBracePairHelp(s, nCurrLeftBraceNum +1, nMaxPairNum);
s.pop_back();
}
// -- check whether we can put a ')'
if( s.size() - nCurrLeftBraceNum < nCurrLeftBraceNum )
{
s.push_back(')');
EnumerateBracePairHelp(s, nCurrLeftBraceNum, nMaxPairNum);
s.pop_back();
}
}
void EnumerateBracePair(int k)
{
if(k<=0)
return;
deque
EnumerateBracePairHelp(s,0,k);
}
int main()
{
EnumerateBracePair(5);
return 0;
}
