generate parenthesis Algorithm
Specific forms of the mark include rounded brackets (also named parenthesis), square brackets, curly brackets (also named braces), and angle brackets (also named chevrons), as well as various less common pairs of symbols. typically deployed in symmetric pairs, an individual bracket may be identify as a left or right bracket or, alternatively, an opening paired bracket or closing paired bracket, respectively, depending on the directionality of the context. Chevrons, ⟨ ⟩, were the earliest type of bracket to look in write English. Desiderius Erasmus coined the term lunula to refer to the rounded parenthesis, (), recalling the shape of the crescent moon.
/**
* Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
*
* For example, given n = 3, a solution set is:
*
* "((()))", "(()())", "(())()", "()(())", "()()()"
*
*/
#include <iostream>
#include <vector>
#include <string>
void generate_parenthesis_helper( int n, int left, int right, std::string curr, std::vector<std::string> & result ) {
if (right == n) {
result.push_back(curr);
} else {
if (left < n) {
generate_parenthesis_helper( n, left + 1, right, curr + '(', result);
}
if (right < left) {
generate_parenthesis_helper( n, left, right + 1, curr + ')', result);
}
}
}
std::vector<std::string> generate_parenthesis( int n ) {
std::vector<std::string> result;
std::string curr{ "" };
generate_parenthesis_helper(n, 0, 0, curr, result);
return result;
}
int main() {
std::vector<std::string> result = generate_parenthesis(3);
for ( auto s : result ) {
std::cout << "{ " << s << " }" << std::endl;
}
return 0;
}
