BiruLyu
6/5/2017 - 12:30 AM

## 22. Generate Parentheses.java

``````"""
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:

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

"""

class Solution(object):

def helper(self,left,right,temp,res):
if left > right:
return;
if left == 0 and right == 0:
res.append(temp);
if left > 0:
self.helper(left - 1, right, temp + '(', res);
if right > 0:
self.helper(left, right - 1, temp + ')', res);

def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
if not n:
return [];

res = [];
self.helper(n,n,"",res);
return res;``````
``````public class Solution {
public List<String> generateParenthesis(int n) {

List<String> res = new ArrayList<String>();
StringBuilder temp = new StringBuilder();
backtracking(n, n, temp, res);
return res;
}

private void backtracking(int left, int right, StringBuilder temp, List<String> res) {
if(left == 0 && right == 0) {
return;
}

if(left > 0) {
temp.append('(');
backtracking(left - 1, right, temp, res);
temp.setLength(temp.length() - 1);
}

if(right > left) {
temp.append(')');
backtracking(left, right - 1, temp, res);
temp.setLength(temp.length() - 1);
}
}
}``````