@@ -0,0 +1,1191 @@
+package GenerateParentheses;%0A%0A%0Aimport java.util.ArrayList;%0Aimport java.util.List;%0A%0A/**%0A * Given n pairs of parentheses, write a function to generate all combinations of well-formed%0A * parentheses.%0A *%0A * For example, given n = 3, a solution set is:%0A * %3Cpre%3E%0A * %5B%0A * %22((()))%22,%0A * %22(()())%22,%0A * %22(())()%22,%0A * %22()(())%22,%0A * %22()()()%22%0A * %5D%0A * %3C/pre%3E%0A */%0Apublic class Solution %7B%0A%0A    private List%3CString%3E dfs(int left, int open, String prefix) %7B%0A        List%3CString%3E r = new ArrayList%3C%3E();%0A        if (left %3C open) %7B%0A            // The left positions is more than opened parentheses%0A            return r;%0A        %7D%0A        if (left == 1) %7B%0A            // The last position must be %22)%22%0A            if (open == 1) %7B%0A                r.add(prefix + %22)%22);%0A            %7D%0A            return r;%0A        %7D%0A        List%3CString%3E openResult = dfs(left - 1, open + 1, prefix + %22(%22);%0A        if (open %3E 0) %7B%0A            List%3CString%3E closeResult = dfs(left - 1, open - 1, prefix + %22)%22);%0A            openResult.addAll(closeResult);%0A        %7D%0A        return openResult;%0A    %7D%0A%0A    public List%3CString%3E generateParenthesis(int n) %7B%0A        // The first position must be %22(%22%0A        return dfs(n * 2 - 1, 1, %22(%22);%0A    %7D%0A%7D

22. Generate Parentheses