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

generateParenthesis.java

/*
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 ArrayList<String> generateParenthesis(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<String> ret = new ArrayList<String>();
        ret.add("");
        
        if(n == 0) return ret;
        
        Queue<ArrayList<String>> queue = new PriorityQueue<ArrayList<String>>();
        queue.offer(ret);
        
        while(!queue.isEmpty() && n > 0) {
            ArrayList<String> cur = queue.poll();
            ArrayList<String> next = new ArrayList<String>();
            for(int j = 0; j < cur.size(); j++) {
                String s = cur.get(j);
                for(int i = 0; i <= s.length(); i++) {
                    String newStr = insert(i, s);
                    if(next.indexOf(newStr) < 0) {
                        next.add(newStr);
                    }
                }
            }
            
            n--;
            
            if(n == 0) {
                return next;
            } else {
                queue.offer(next);
            }
        }
        return ret;
    }
    
    public String insert(int index, String str) {
        String left = str.substring(0, index);
        String right = str.substring(index, str.length());
        return new String(left+"()"+right);
    }
}