leetcode 生成括号 java

生成括号

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

分析

经典的回溯问题，其实和电话号码那道题一样https://blog.csdn.net/qq_43491066/article/details/102876153

但是区别在于，电话号码是任意组合都复合要求，而这道题括号需要匹配。
我先画一个完整的“（）”，发现再加“（）”的话很容易有重复还分不清楚。
于是意识到不能整个整个的加“（）”
咱们来分析一下
首先：
加（
这时候无论再加（还是）都是合法的。
①：
（），接下来还有两对括号加，依然发现（
无论怎么加都合理，而）必须在（之后加并且加再后边。
画出一个图就非常清楚(电脑上不方便画图我就不画了）
所以递归思路是这样的：
1.如果剩余的（数量大于0，那么直接将（加上去
2.如果剩余的）数量大于（数量，加）,保证括号合法
3.如果左括号右括号剩下的数量都是0，则将整个字符串加到list里保存。

如果还没有看懂，看下边的分析：

举个例子n=2

(

我们发现(的数量小于n，我们继续填入( 当然这个时候(的数量也小于）,所以也可以填入）

( (

或者

( )

我们发现(等于n了，我们就不再填入(了，然后我们考虑)的数量小于(，所以我们填入(。

( ( ) )

或者

( ) ( )

比较巧妙地地方就在于left<right的操作使得括号合理

java代码

最后附上代码：

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res=new ArrayList();
        // str用来暂时存每个分支的（）
        String str=new String();
        generate(res,str,n,n);
        return res;
        
    }
    public void generate(List<String> list,String str,int left,int right){//都为0，说明（）用完了，该return了
        if(left==0&&right==0){
            list.add(str);
            return;
        }//还剩左括号，直接放
        if(left>0){
            generate(list,str+'(',left-1,right);
        }//右括号数量大于左括号才能放
         if(right>left){
            generate(list,str+')',left,right-1);
        }
    }
}

上方代码通过测试 耗时1ms
大佬代码的数组映射也是高效率的好办法：

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        char[] items = new char[2 * n];
        items[0] = '(';
        gen(n, 1, 0, items, res);
        return res;
    }

    private void gen(int n, int left, int right, char[] items, List<String> res) {

        if (left == n && right == n) {
            res.add(String.copyValueOf(items));
            return;
        }
        if (left > n || right >n || left < right) {
            return;
        }

        items[left + right] = '(';
        gen(n, left + 1, right, items, res);

        items[left + right] = ')';
        gen(n, left, right+1, items, res);
    }
}

总结

这道题的区别在于合法 ，画个草稿就能发现合法的要点是）要后放