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:
[ "((()))", "(()())", "(())()", "()(())", "()()()"]
Subscribe to see which companies asked this question.

題目

給定 n 對括號，請寫一個函數(shù)以將其生成新的括號組合，并返回所有組合結(jié)果。
樣例
給定 n = 3, 可生成的組合如下:
"((()))", "(()())", "(())()", "()(())", "()()()"

分析

針對一個長度為2n的合法排列，第1到2n個位置都滿足如下規(guī)則：左括號的個數(shù)大于等于右括號的個數(shù)。所以，我們就可以按照這個規(guī)則去打印括號：假設(shè)在位置k我們還剩余l(xiāng)eft個左括號和right個右括號，如果left>0，則我們可以直接打印左括號，而不違背規(guī)則。能否打印右括號，我們還必須驗證left和right的值是否滿足規(guī)則，如果left>=right，則我們不能打印右括號，因為打印會違背合法排列的規(guī)則，否則可以打印右括號。如果left和right均為零，則說明我們已經(jīng)完成一個合法排列，可以將其打印出來。通過深搜，我們可以很快地解決問題，針對n=2，問題的解空間如下

Paste_Image.png

代碼

public class Solution {
    /**
     * @param n n pairs
     * @return All combinations of well-formed parentheses
     */
     public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> result = new ArrayList<String>();
        if (n <= 0) {
            return result;
        }
        helper(result, "", n, n);
        return result;
    }
    
    public void helper(ArrayList<String> result,
                       String paren, // current paren
                       int left,     // how many left paren we need to add
                       int right) {  // how many right paren we need to add
        if (left == 0 && right == 0) {
            result.add(paren);
            return;
        }

        if (left > 0) {
            helper(result, paren + "(", left - 1, right);
        }
        
        if (right > 0 && left < right) {
            helper(result, paren + ")", left, right - 1);
        }
    }
}