22 Generate Parentheses

Leetcode

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

---

不断递归生成下一个位置的括号。递归的时候传递剩余左右括号数量，如果剩下的左右括号数量相等，则当前位置只能放置左括号，否则两者都可以。直到放置完毕生成字符串。

class Solution {
    public List<String> generateParenthesis(int n) {
        char[] arr=new char[n << 1];
        List<String> ret=new ArrayList<>();
        recur(n,n,0,arr,ret);
        return ret;
    }
    
    private void recur(int open, int close, int index, 
                       char[] arr, List<String> ret){
        if(index==arr.length){
            ret.add(String.valueOf(arr));
            return;
        }
        if(open==close){
            arr[index]='(';
            recur(open-1, close, index+1, arr, ret);
        } else {
            if(open>0){
                arr[index]='(';
                recur(open-1, close, index+1, arr, ret);
            }
            arr[index]=')';
            recur(open, close-1, index+1, arr, ret);
        }
    }
}