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:

“((()))”, “(()())”, “(())()”, “()(())”, “()()()”

public class Solution { public List generateParenthesis(int n) { } }

This problem is selected from LeetCode.

## Solution

We can convert the problem as follows:

find all the combinations of n “(” and n “)” such that for any point in a combination, the number of “)” is less than or equal to the

number of “(“. With this condition, we could solve the problem by recursion. Setup two variables left and right to track the number of

“(” and “)” still available. If left is greater than 0, we could add more “(“. If right is greater than left, we could add more “)”. When

right and left are all equal to 0, a complete combination is found.

public class Solution { public List generateParenthesis(int n) { List result = new LinkedList<>(); generate(result, "", n, n); return result; } public void generate(List result, String combination, int left, int right) { if(left == 0 && right == 0) result.add(combination); if(left>0) generate(result, combination+"(", left-1, right); if(right > left) generate(result, combination+")", left, right-1); } }

PhilipOctober 9, 2016 at 9:11 amIn the solution the recursive function call is wrong (the name of it): instead of buildResult it should be ‘generate’

Tge app is really cool, thanks for your effort!