博客

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:

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

题目分析：只要保证左括号个数大于等于右括号且小于等于n即可，DFS构造

public class Solution {

    public void DFS(int l, int r, int n, String str, List<String> ans) {
        if (l == n && r == n) {
            ans.add(str);
            return;
        }
        if (l > r) {
            DFS(l, r + 1, n, str + ")", ans);
        }
        if (l < n) {
            DFS(l + 1, r, n, str + "(", ans);
        }
    }
    
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        DFS(0, 0, n, "", ans);
        return ans;
    }
}