# Generate Parantheses

Companies:

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 ` 2`2n` ` 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;
}
```
Scroll to Top

### Full Stack Integrated Bootcamp Free Trial

• Please enter a number from 7000000000 to 9999999999.