欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【LeetCode】 22. 生成括号 回溯 JAVA

程序员文章站 2024-01-11 17:17:52
...

题目

题目传送门:传送门(点击此处)
【LeetCode】 22. 生成括号 回溯 JAVA

题解

其实这道题目还是有难度的,如果没有放在回溯模块儿下,很难想到使用回溯的解决方案,也许是我太菜了哈哈哈

思路

  1. 括号是一对一对生成的,所以,必须先有 ( ,再有 )
  2. 每次递归,只需要有 () 的数量,再有当前拼接成的字符串,就可以进行递归,获得结果。
  3. 递归就分为四种情况,() 都有可能有和没有,所以根据这四种情况进行判断就可以了

代码

class Solution {

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

    public List<String> generateParenthesis(int n) {
        if (n < 0) return res;
        generate(n, 0, "");
        return res;
    }

    // lLeft: 左括号剩余量
    // rRight: 右括号剩余量
    // preStr: 上一次generate的括号字符串
    private void generate(int lLeft, int rLeft, String preStr) {
        if (lLeft == 0 && rLeft == 0) {
            res.add(preStr);
            return;
        } else if (lLeft == 0 && rLeft > 0) {
            String str = preStr + ")";
            int l = lLeft;
            int r = rLeft - 1;
            generate(l, r, str);
        } else if (lLeft > 0 && rLeft > 0) {
            String str1 = preStr + "(";
            int l = lLeft - 1;
            int r = rLeft + 1;
            generate(l, r, str1);
            String str2 = preStr + ")";
            l = lLeft;
            r = rLeft - 1;
            generate(l, r, str2);
        } else if (lLeft > 0 && rLeft == 0) {
            String str = preStr + "(";
            int l = lLeft - 1;
            int r = rLeft + 1;
            generate(l, r, str);
        }
        return;
    }
}