LeetCode : 22. Generate Parentheses 生成括号组合

偏执的太偏执、 2021-06-24 16:10 403阅读 0赞

**试题**  
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

\[  
“((()))”,  
“(()())”,  
“(())()”,  
“()(())”,  
“()()()”  
\]  
**代码**  
递归方法：  
当开始为空字符串"“时，我们有两种添加方式：一是加”(“另一是加”)"。所以每次递归调用都存在两种情况。  
但是要明白，如果我们添加的方式造成了不合要求，这时肯定会出现两种情况：一是添加左括号数量超过最大值，另外就是右括号数量大于左括号数量。所以我们可以通过剪枝方式避免这些情况。

class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> ans = new ArrayList<>();
            backtrack(ans, "", 0, 0, n);
            return ans;
        }
        
        public void backtrack(List<String> ans, String cur, int open, int close, int max){
            if(cur.length()==max*2){
                ans.add(cur);
                return;
            }
            if(open<max){
                backtrack(ans, cur+"(", open+1, close, max);
            }
            if(close<open){
                backtrack(ans, cur+")", open, close+1, max);
            }
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，403人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-form

谁践踏了优雅/ 2022年07月29日 09:29/ 0 赞/ 198 阅读

相关 Leetcode——22. Generate Parentheses

1. 概述 1.1 题目 Given n pairs of parentheses, write a function to generate all combin

淩亂°似流年/ 2022年06月12日 22:14/ 0 赞/ 185 阅读

相关 [Leetcode][python]Generate Parentheses/括号生成

题目大意给定n，生成n对括号，必须正常关闭所有符号解题思路深度优先、回溯法典型代表代码 class Solution(object):

淡淡的烟草味﹌/ 2022年06月09日 03:29/ 0 赞/ 497 阅读

相关 22. Generate Parentheses（生成括号）

Given n pairs of parentheses, write a function to generate all combinations of well-form

分手后的思念是犯贱/ 2022年06月08日 09:55/ 0 赞/ 197 阅读

相关 LeetCode 22.Generate Parentheses (括号生成)

题目描述：给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。例如，给出 n =3，生成结果为： [ "((

叁歲伎倆/ 2022年05月11日 00:46/ 0 赞/ 210 阅读

相关 LeetCode：22. Generate Parentheses（生成匹配括号）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

本是古典何须时尚/ 2022年04月04日 06:14/ 0 赞/ 248 阅读

相关 [Leetcode]Generate Parentheses(生成括号）

一、题目描述 Given n pairs of parentheses, write a function to generate all combinations of

我就是我/ 2022年02月28日 06:20/ 0 赞/ 228 阅读

相关 leetcode题解第22题 Generate Parentheses（括号生成）

题目的大意如下： > 给定一个整数n，代表括号的对数，请给出所有合法的括号组合。样例输入： > 3 样例输出： > \[ > “((()))”, > “((

我不是女神ヾ/ 2022年02月28日 00:20/ 0 赞/ 213 阅读

相关 [LeetCode]22. Generate Parentheses括号生成

Given n pairs of parentheses, write a function to generate all combinations of well-form

冷不防/ 2021年12月20日 23:05/ 0 赞/ 231 阅读

相关 LeetCode : 22. Generate Parentheses 生成括号组合

试题 Given n pairs of parentheses, write a function to generate all combinations of well

偏执的太偏执、/ 2021年06月24日 16:10/ 0 赞/ 404 阅读