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:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Solution

public class Solution {

    //List<String> ans = new ArrayList<String>();

    Map<Integer, List<String>> map = new HashMap<Integer, List<String>>();

    public List<String> generateParenthesis(int n) {
        /*
        search(n, n, "");
        */

        if(map.containsKey(n)) return map.get(n);
        List<String> ans = new ArrayList<String>();

        if(n == 1) {
            ans.add("()");
        } else {
            for(int i = 0; i <= n-1; i++) {
                List<String> left = generateParenthesis(i);
                List<String> right = generateParenthesis(n-i-1);
                if(left.size() == 0) left.add("");
                if(right.size() == 0) right.add("");
                for(String l: left) {
                    for(String r: right) {
                        ans.add("(" + l + ")" + r);
                    }
                }
            }
        }

        map.put(n, ans);
        return ans;
    }

    /*
    void search(int left, int right, String path) {
        if(left == 0 && right == 0) {
            ans.add(path);
            return;
        }
        if(left != 0) search(left-1, right, path + "(");
        if(left < right) search(left, right-1, path + ")");
    }
    */


}