c*****e
发帖数: 74 | 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<<*iter;
}
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;
} | b*****e
发帖数: 474 | 2 很不错了。细节可以再推敲一下，算法本身（基于DFS的递归）没问题，C++
的掌握也不错。当个 developer 够了哈。
我的版本，给你参考一下吧：
#include
#include // i like arrays
#include // for atoi()
using namespace std;
void print_parens(int n) {
static vector s; // i just use static vars to save parameter
static numLeft = 0; // passing
static numRight = 0;
if (n<0) return;
if (n==0) {
for( int i=0; i
// save the extra recursion when there are n '('s already -
// so you don't need to construct a size 2*n string
for( int i=0; i
cout << endl;
return;
}
// DFS steps:
s.push_back('('); numLeft++;
print_parens(n-1); // you don't need to check numLeft
s.pop_back(); numLeft--;
if (numRight
s.push_back(')'); numRight++;
print_parens(n);
s.pop_back(); numRight--;
}
}
int main(int argc, char *argv[]) {
if ( argc == 1 ) { cour << "print_paren n" << endl; }
else {
int n = atoi(argv[1]);
print_parens(n);
}
return 0;
} |
|
