## All combinations of balanced parentheses (Generate Parentheses)

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:
“((()))”, “(()())”, “(())()”, “()(())”, “()()()”

Thoughts:
Recursion. Base case is which the solution has size of $2*n$. Recursive step: each time we count number of open parenthesis and closed parenthesis. If open == closed, then we have to add open parenthesis. If open > closed, we can add open parenthesis as long as we do not exceed $n$. We can also add closed parenthesis.

Code (Java):

```import java.util.ArrayList;
public class Solution {
public ArrayList<String> generateParenthesis(int n) {
ArrayList<String> solutions = new ArrayList<String>();
recursion(n, new String(), solutions);
return solutions;
}

private void recursion(int n, String str, ArrayList<String> sol) {
if(str.length() == 2 * n)
else {
int left = 0;
int right = 0;
for(int i = 0; i < str.length(); ++i) {
if(str.charAt(i) == '(')
left++;
if(str.charAt(i) == ')')
right++;
}
if(left == right)
recursion(n, str + "(", sol);
else if(right < left) {
if(left < n)
recursion(n, str + "(", sol);
recursion(n, str + ")", sol);
}
}
}
}

Code (C++):
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> solutions;
string solution;
recursion(n, solution, solutions);
return solutions;
}

void recursion(int n, string solution, vector<string> &solutions) {
if(solution.size() == 2*n) {
solutions.push_back(solution);
} else {
int left = 0;
int right = 0;
for(int i = 0; i < solution.size(); ++i) {
if(solution[i] == '(')
left++;
if(solution[i] == ')')
right++;
}
if(left == right)
recursion(n, solution + "(", solutions);
else if(left > right) {
if(left < n)
recursion(n, solution + "(", solutions);
recursion(n, solution + ")", solutions);
}
}
}
};

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5b27fee11089f', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5b27fee1108ed',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5b27fee1108f0',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});

Related
```

1. Poonam
Feb 17, 2014 @ 06:07:10

Another way to solve this would be

public class Parenthesis {

public static void main(String[] args) {
int n = 3;
char[] str = new char[n*2];
printParenthesis(n,n,str,0);
}

private static void printParenthesis(int lCount, int rCount, char[] str,
int count) {
if(lCount < 0 || rCount 0){
str[count] = ‘(‘;
printParenthesis(lCount-1, rCount, str, count+1);
}
if(rCount > lCount){
str[count] = ‘)’;
printParenthesis(lCount, rCount-1, str, count+1);
}
}
}
}