括号生成（列出所有括号的搭配情况）

ゞ浴缸里的玫瑰 2021-06-22 15:38 486阅读 0赞

//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。  
//  
// 示例：  
//  
// 输入：n = 3  
//输出：\[  
// “((()))”,  
// “(()())”,  
// “(())()”,  
// “()(())”,  
// “()()()”  
// \]  
//  
// Related Topics 字符串 回溯算法

//思路1：数学归纳法 代码不好写  
//思路2：递归、深度优先遍历DFS 对排列组合进行剪枝，1、如果局部就不合法了，就不再递归 2、记录左右括号的使用量

import java.util.ArrayList;
    
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution { 
    	public List<String> generateParenthesis(int n) { 
    		List<String> result = new ArrayList<>();
    		doGenerate(0, 0, n, "", result);
    		return result;
    	}
    
    	/** * @param left 已有的左括号个数 * @param right 已有的右括号个数 * @param n 入参n * @param sb 当前字符串 * @param result 字符串结果列表 * @return */
    	public void doGenerate(int left, int right, int n, String str, List<String> result) { 
    		if (left == n && right == n) { 
    			result.add(str);
    			return;
    		}
    		// 左括号可以直接加
    		if (left < n) { 
    			doGenerate(left + 1, right, n, str + "(", result);
    		}
    		// 右括号小于左括号，且小于n，可以加右括号
    		if (left > right && right < n) { 
    			doGenerate(left, right + 1, n, str + ")", result);
    		}
    	}
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 22括号生成

一、前言标签：回溯算法。问题来源LeetCode 22 难度：中等。问题链接：[https://leetcode-cn.com/problems/generat

旧城等待，/ 2023年03月01日 12:21/ 0 赞/ 26 阅读

相关 LeetCode-22 括号生成

[LeetCode22][] dp做法：包含n个括号组的字符串结果，取决于n-1个括号组的字符串结果假设n-1个括号组的字符串形式有k种则有：n个括号组的字符串

柔光的暖阳◎/ 2022年12月14日 03:43/ 0 赞/ 233 阅读

相关 22. 括号生成

> 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。 > > 示例 1： > > 输入：n = 3 > 输出：\["(((

雨点打透心脏的1/2处/ 2022年10月08日 05:40/ 0 赞/ 189 阅读

相关 22. 括号生成

[https://leetcode-cn.com/problems/generate-parentheses/][https_leetcode-cn.com_problems_

系统管理员/ 2022年09月09日 00:24/ 0 赞/ 221 阅读

相关 n对括号组合的所有情况

public class KuohaoTest { public static Set<String> selectAll(int n){

布满荆棘的人生/ 2022年06月16日 04:08/ 0 赞/ 151 阅读

相关【LeetCode】22. 括号生成

题目链接：[https://leetcode-cn.com/problems/generate-parentheses/description/][https_leetcode

梦里梦外;/ 2022年05月03日 00:28/ 0 赞/ 211 阅读

相关 leetcode 括号生成

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

妖狐艹你老母/ 2022年03月27日 08:16/ 0 赞/ 223 阅读

相关括号对的生成

题目描述：来源：[https://leetcode-cn.com/problems/generate-parentheses/][https_leetcode-cn.com_p

男娘i/ 2021年12月17日 01:07/ 0 赞/ 252 阅读

相关 22. 括号生成

总结：用相同的方法是有两种情况，一种是地柜，一种是循环。 include<vector> include<iostream> include<st

男娘i/ 2021年11月02日 05:22/ 0 赞/ 339 阅读

相关括号生成（列出所有括号的搭配情况）

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

ゞ浴缸里的玫瑰/ 2021年06月22日 15:38/ 0 赞/ 487 阅读