每天一题LeetCode【第19天】

T22. Generate Parentheses【Medium】

题目

给定 n 对圆括号，写一个函数来生成正确形式的括号的所有组合。

例如，给出 n=3 ,一个解集是：

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

思路

这个代码的思路很简单，就是分类讨论的感觉，正确的括号组合满足下列两个条件：
① （ 的数量一定小于max

② ）的数量小于等于（ 的数量

设（ 的数量为 open,）的数量为 close ，

当 open < max 且 close = open时 后面只能加 （, 例如 str="()" 时

当 open < max 且 close < open时 后面既能加 （ 也能加 ），例如 str="()（" 时

代码

代码取自 Top Solution，稍作注释

public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<String>();
        backtrack(list, "", 0, 0, n);
        return list;
    }
    
    public void backtrack(List<String> list, String str, int open, int close, int max){
        //若长度达到 max*2 说明完整了，加入到 list 里面
        if(str.length() == max*2){
            list.add(str);
            return;
        }
        //当 open<max 时可以添加 （，并 open+1
        if(open < max)
            backtrack(list, str+"(", open+1, close, max);
        //当 close < open 时可以添加 ）,并 close+1
        if(close < open)
            backtrack(list, str+")", open, close+1, max);
    }

补充

这里方法中传参 list 传递了 list 的地址，两个 list 指向同一块区域，所以改了任意一个，另一个也会改~

想具体了解一下 java 参数传递，我看了这个 blog: http://blog.sina.com.cn/s/blog_4b622a8e0100c1bo.html