## 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);
}
}
}
};

div.wpmrec2x{max-width:610px;}
div.wpmrec2x div.u > div{float:left;margin-right:10px;}
div.wpmrec2x div.u > div:nth-child(3n){margin-right:0px;}

(function(g,\$){if("undefined"!=typeof g.__ATA){
}})(window,jQuery);

var o = document.getElementById('crt-834599882');
if ("undefined"!=typeof Criteo) {
var p = o.parentNode;
p.style.setProperty('display', 'inline-block', 'important');
o.style.setProperty('display', 'block', 'important');
} else {
o.style.setProperty('display', 'none', 'important');
o.style.setProperty('visibility', 'hidden', 'important');
}

var o = document.getElementById('crt-342196338');
if ("undefined"!=typeof Criteo) {
var p = o.parentNode;
p.style.setProperty('display', 'inline-block', 'important');
o.style.setProperty('display', 'block', 'important');
} else {
o.style.setProperty('display', 'none', 'important');
o.style.setProperty('visibility', 'hidden', 'important');
}

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);
}
}
}
}