博客

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:


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


============

Analysis:

Use recursive approach.  For each recursive call, there are 2 cases:

1. Number of “(” larger then number of “)” -> in this case, we can add either “(” or “)” in current recursive call

2. Number of “(” equal to number of “)” -> in this case, only “(” can be added.

Note that there is no case of number of “(” less then number of “)”, because when they are equal, we always add “(” (case 2).

Recursive function exit:

when number of “(” reached n, then just add remaining “)” and return.

public class Solution {
    public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> res = new ArrayList<String>();
        if(n==0) {
            res.add("");
            return res;
        }
        
        helper(n,0,0,res,"");
        return res;
    }
    
    public void helper(int n, int left, int right, ArrayList<String> res, String temp){
        // exit: all ( appeared
        if(left == n){
            for (int i=0; i<n-right; i++) 
                temp = temp + ")";
            res.add(temp);
            return;
        }
        
        // case1: number of ( > number of )
        if(left>right){
            helper(n, left+1, right, res, temp + "(");
            helper(n, left, right+1, res, temp + ")");
        }
        
        // case2: number of ( == number of )
        else helper(n, left+1, right, res, temp + "(");
    }
}