22. Generate Parentheses（生成括号）

分手后的思念是犯贱 2022-06-08 09:55 147阅读 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:

[
      "((()))",
      "(()())",
      "(())()",
      "()(())",
      "()()()"
    ]

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

**题目大意：**给定一个整数n，求出n对括号所有合理的组合形式。例如，给定n=3,则所有合理的组成形式为上述5种。

**解题思路：**递归，每次传递的参数为：括号数n，当前已有的左括号数left，当前已有的右括号数right，当前的括号组成字符串s。参数初始分别为：n，0，0，""。

递归函数每次先判断是否已经得到满足条件的组合形式，即left+right==n，如果满足，添加进结果集合res，并return。否则继续进行判断，如果left<n，则可以添加一个左括号，在left<n的情况下，如果right<left，则可以添加一个右括号。如果left=n（不可能>n），那么只能添加一个右括号。

**解题代码：**（3ms，beats 48.34%）

class Solution {
        List<String> res = null;
    
    	public void generate(int n, int left, int right, String s) {
    		if (left + right == 2 * n) {
    			res.add(s);
    			return;
    		}
    		if (left < n) {
    			generate(n, left + 1, right, s + "(");
    			if (right < left) {
    				generate(n, left, right + 1, s + ")");
    			}
    		} else {
    			generate(n, left, right + 1, s + ")");
    		}
    	}
    
    	public List<String> generateParenthesis(int n) {
    		res = new ArrayList<>();
    		generate(n, 0, 0, "");
    		return res;
    	}
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 Generate Parentheses（C++括号生成）

解题思路：（1）使用回溯法，注意值传递而不是址传递 class Solution { public: bool helper(string

野性酷女/ 2022年11月06日 10:55/ 0 赞/ 110 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相关 22. Generate Parentheses

description: Given n pairs of parentheses, write a function to generate all combinati

桃扇骨/ 2021年12月24日 19:07/ 0 赞/ 206 阅读

相关 [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 赞/ 186 阅读

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

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

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