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:

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

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        if(n>0){
            generateParenthesis("", n, n, result);
        }
        return result;
    }
   
    public void generateParenthesis(String prefix, int left, int right, List<String> result){
        if(left>right){
            return;
        }
        if(left==0){
             for(int i=0;i<right;i++){
                 prefix+=")";
             }
             result.add(prefix);
             return;
        }
        if(left<right){
            generateParenthesis(prefix+")", left, right-1, result);
        }
        generateParenthesis(prefix+"(", left-1, right, result);    
    }
}

Note: The key point of this problem is when generating parentheses, the number of left parentheses being used so far is always larger than the number of right parentheses. In the algorithm. left and right means # of parentheses not being used so far.

Share