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

谁借莪１个温暖的怀抱￠ 2021-06-10 20:38 249阅读 0赞

## <table>   <tbody>    <tr>     <td><font>题目</font></td>    </tr>   </tbody>  </table> ##

题目传送门：[传送门（点击此处）][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]

## <table>   <tbody>    <tr>     <td><font>题解</font></td>    </tr>   </tbody>  </table> ##

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

### 思路 ###

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;
        }
    }

[Link 1]: https://leetcode-cn.com/problems/generate-parentheses/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/9993c8ca63c94dd5ab3a4ad347de7c10.png