• [x] ### DFS

22.Generate Parentheses

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

For example, givenn= 3, a solution set is:

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

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        if (n == 0) {
            return ans;
        }
        helper(ans, "", n,n);
        return ans;
    }
    public void helper(List<String> ans,String path,  int left, int right) {
        if (left > right) {
            return;
        }
        if (left == 0 && right == 0) {
            ans.add(path);
            return;
        }
        if (left > 0) {
            helper(ans, path + "(", left - 1, right);
        }
        if (right > 0) {
            helper(ans, path + ")", left , right - 1);
        }
    }
}

如果没有 if(left > right)限制的话，时间复杂度是o(2 ^ n)

符合卡特兰数，O(n!)

space O(n)