[LeetCode]--22. Generate Parentheses

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 List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<String>();
        if (n == 0)
            return res;
        dfs(res, "", n, n);
        return res;
    }

    private void dfs(List<String> res, String tem, int left, int right) {
        if (0 == left && 0 == right) {
            res.add(tem);
            return;
        } else if (left > 0)
            dfs(res, tem + '(', left - 1, right);
        if (left < right)
            dfs(res, tem + ')', left, right - 1);
    }

这种递归到最后自然就都加上去了。