generate parentheses

https://leetcode.com/problems/generate-parentheses/
经典递归，思路如下：
用left 和 right 表示左边和右边括号的数目，有如下几种边界条件：

left < right, 表示产生的括号中，右边的括号多于左边的，e.g. “)” 这种情况not valid，直接返回
left 和 right 均等于n，则表示这是一个符合条件的组合，输出。
left < n，则表示左边的括号还可以继续增加

e.g.
generateParenthesis(3);
((()))
(()())
(())()
()(())
()()()
体会下递归过程

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

public List<String> (int n) {
    helper("", 0, 0, n);
    return ans;
}

public void helper(String path, int left, int right, int n) {
    if (left < right)
        return;
    if (left == n && right == n) {
        ans.add(path);
        return;
    }
    if (left < n)
        helper(path + "(", left + 1, right, n);

    helper(path + ")", left, right + 1, n);
}

generate parentheses

近期文章

近期评论

标签

热门

文章归档

分类目录

功能