For a given n
, generate all strings of size 2*n
with well formed parantheses.
Example Test Cases
Sample Test Case 1
N: 2
Expected Output:
()()
(())
Sample Test Case 2
N: 3
Expected Output:
((()))
(()())
()(())
(())()
()()()
Solution
We can solve this problem by generating all the possible strings of length 2^n
, such that each character in the string is either (
or )
, and then printing only those strings which are balanced. There will be a total of
2n 2
such strings.
Implementation
We can implement the above algorithm using backtracking as shown below:
Implementation
#include <iostream> #include <vector> #include <string> using namespace std; // Function to check if the string is valid paranthesis or not. bool isValid(string str) { int cnt = 0; for(int i = 0; i < str.size(); i++) { if (str[i] == '(') { cnt++; } else if (str[i] == ')') { cnt--; } if (cnt < 0) { return false; } } if (cnt == 0) { return true; } return false; } // Recursive function to backtrack and generate all the possible combinations void backtrack(string& str, int i, int n) { // Once the full string is generate, print the string if it is valid. if (i == n) { if (isValid(str)) { cout << str << "\n"; } } else { str.push_back('('); backtrack(str, i + 1, n); str.pop_back(); str.push_back(')'); backtrack(str, i + 1, n); str.pop_back(); } } void generateParenthesis(int n) { string str; backtrack(str, 0, n); } int main() { int n = 3; generateParenthesis(2*n); return 0; }