Generate Parentheses 427

Question

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

Example

Given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

Solution

要求所有组合，用递归。

用temp记录当前的括号组合，用left记录左括号数量，用right记录右括号数量。

1. 如果在某次递归时，左括号的个数大于右括号的个数，说明此时生成的字符串中右括号的个数大于左括号的个数，即会出现')('这样的非法串，所以这种情况直接返回，不继续处理。

2. 如果left和right都为0，则说明此时生成的字符串已有3个左括号和3个右括号，且字符串合法，则存入结果中后返回。

3. 如果以上两种情况都不满足，若此时left大于0，则调用递归函数，注意参数的更新（左括号数量减少1，temp+"("），若right大于0，则调用递归函数，同样要更新参数（右括号数量减少1,temp+")"）。

4. 如果左括号数量已经为0而右括号数量不为0，可以直接将右括号补全而不调用递归

代码如下：

public class Solution {
    /**
     * @param n n pairs
     * @return All combinations of well-formed parentheses
     */
    public ArrayList<String> generateParenthesis(int n) {
        // Write your code here
        ArrayList<String> res = new ArrayList<String>();
        if(n < 1){
            return res;
        }
        helper(n, n, "", res);
        return res;
    }

    private void helper(int left, int right, String temp, ArrayList<String> res){
        if(left < 0 || right < 0 || left > right){
            return;
        }

        if(left == 0 && right == 0){
            res.add(temp);
            return;
        }

        if(left == 0){
            while(right != 0){
                temp += ")";
                right--;
            }
            res.add(temp);
            return;
        }

        helper(left - 1, right, temp + "(", res);
        helper(left, right - 1, temp + ")", res);
    }
}