（LeetCode）Java 求解括号的生成

Myth丶恋晨 2023-01-12 04:13 18阅读 0赞

### 文章目录 ###

*   *  一、题目
     *  二、代码
     *  三、总结

## 一、题目 ##

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]

--------------------

解析：  
这个题乍一看，感觉挺难，很类似前几天那个 [求解电话号码][Link 1]，但是这个括号和具体字母又不一样，不能那样计算。

具体思路还是采用递归回溯，当剩余的左右括号数目相同时，只能先添加左括号，当剩余的右括号数目大于左括号数目时，既可以添加左括号，也可以添加右括号；

> 类似，n=3, 当str=()，剩余左右括号数目都为2，所以下一个只能添加左括号，str = ()(  
> n=3，当 str=()(，剩余左括号 1，右括号2，所以下一个可以添加左括号，也可以添加右括号：str = ()() 或者 str = ()((

虽然这里也涉及字符串的拼接，但是如果这里使用 StringBuilder，有点麻烦，只要加，就涉及剔除，所以这里还是选用 String吧，空间使用也没差多少。

## 二、代码 ##

class Solution { 
        List<String> res = new ArrayList<>();
    
        public List<String> generateParenthesis(int n) { 
            if (n <= 0) { 
                return res;
            }
            getParenthesis("", n, n);
            return res;
        }
    
        private void getParenthesis(String str, int left, int right) { 
            if (left == 0 && right == 0) { 
                res.add(str);
                return;
            }
            if (left == right) { 
                //剩余左右括号数相等，下一个只能用左括号
                getParenthesis(str + "(", left - 1, right);
            } else { 
                //剩余左括号小于右括号，下一个可以用左括号也可以用右括号
                if (left > 0) { 
                    getParenthesis(str + "(", left - 1, right);
                }
                getParenthesis(str + ")", left, right - 1);
            }
        }
    }

## 三、总结 ##

该题主要还是递归回溯的运用，希望记住这种解题方法

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]: /images/20221119/a722c001984d4d9a816aa5783b220cb1.png
[Link 1]: https://blog.csdn.net/nanhuaibeian/article/details/113058780