# LeetCode 22：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:

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

1：左右括号都有n个，List<String>里每个元素长度都是n*2

2：当字符串长度达到了n*2，可以添加到List<String>里

3：左括号可以随意添加，没限制

4：右括号只能在当前右括号数量比左括号数量小的时候添加，否则新来的右括号就没法匹配了；

Java源码如下

`package com.maoxiaomeng;import java.util.ArrayList;import java.util.List;/** * Copyright (C), 2014-2018, maoxiaomeng.com * FileName: Solution * Author:   lihui * Date:     2018/4/14 00:37 */public class Solution {    public List<String> generateParenthesis(int n) {        List<String> myList = new ArrayList<String>();        if (n < 1) {            return myList;        }                String currentStr = "";        recursionParenthesis(myList, currentStr, 0, 0, n);        return myList;    }        public void recursionParenthesis(List<String> list, String currentStr,                                      int left, int right, int n) {        if (currentStr.length() == n * 2) {            list.add(currentStr);            return;        }                if (left < n) {            recursionParenthesis(list, currentStr + "(", left + 1, right, n);        }                if (left > right) {            recursionParenthesis(list, currentStr + ")", left, right + 1, n);        }    }}`

1：以剩下未传入的括号为基准

2：当剩下的左右括号都没了，结束

3：左括号随便加，剩下的左括号就随便减少

4：当剩下的左括号比右括号少，也就是左括号用出去的更多，可以加右括号，同时剩下的右括号减少

`package com.maoxiaomeng;import java.util.ArrayList;import java.util.List;/** * Copyright (C), 2014-2018, maoxiaomeng.com * FileName: Solution * Author:   lihui * Date:     2018/4/14 00:37 */public class Solution {    public List<String> generateParenthesis(int n) {        List<String> myList = new ArrayList<String>();        if (n < 1) {            return myList;        }                String currentStr = "";        recursionParenthesis(myList, currentStr, n, n);        return myList;    }        public void recursionParenthesis(List<String> list, String currentStr,                                      int left, int right) {        if (left == 0 && right == 0) {            list.add(currentStr);            return;        }                if (left > 0) {            recursionParenthesis(list, currentStr + "(", left - 1, right);        }                if (left < right) {            recursionParenthesis(list, currentStr + ")", left, right - 1);        }    }}`