Leetcode之回溯法专题-22. 括号生成(Generate Parentheses)

时间:2021-03-30 00:19:25

Leetcode之回溯法专题-22. 括号生成(Generate Parentheses)

给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。

例如,给出 n = 3,生成结果为:

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

分析:给定一个n,生成所有可能的括号组合。

举个例子,n=3,需要生成三个括号,那最后的长度是6,即2*n,那我们字符的数量到2*n的时候应该停下。

接下来我们写出递归函数:

    public void dfs(int n, int step, String str, int left, int right) {
if (step == n) {
ans.add(str);
return;
}
if (left < n / 2) {
dfs(n, step + 1, str + "(", left + 1, right);
}
if (left > right) {
dfs(n, step + 1, str + ")", left, right + 1);
} }

函数中用left存左括号的数量,right存储右括号的数量,step存现在的括号数量,n是需要括号的总数量。

最后的AC代码为:

class Solution {
List<String> ans = null; public void dfs(int n,int step,String str,int left,int right){
if(step == n){
ans.add(str);
return;
}
if(left<n/2){
dfs(n,step+1,str+"(",left+1,right);
}
if(left>right){
dfs(n,step+1,str+")",left,right+1);
} } public List<String> generateParenthesis(int n) {
ans = new ArrayList<>(); dfs(2*n,0,"",0,0);
return ans;
} }

Leetcode之回溯法专题-22. 括号生成(Generate Parentheses)的更多相关文章

  1. LeetCode 22&period; 括号生成&lpar;Generate Parentheses&rpar;

    22. 括号生成 22. Generate Parentheses 题目描述 给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合. 例如,给出 n = 3,生成结 ...

  2. Leetcode之回溯法专题-37&period; 解数独(Sudoku Solver)

    Leetcode之回溯法专题-37. 解数独(Sudoku Solver) 编写一个程序,通过已填充的空格来解决数独问题. 一个数独的解法需遵循如下规则: 数字 1-9 在每一行只能出现一次.数字 1 ...

  3. Leetcode之回溯法专题-216&period; 组合总和 III(Combination Sum III)

    Leetcode之回溯法专题-216. 组合总和 III(Combination Sum III) 同类题目: Leetcode之回溯法专题-39. 组合总数(Combination Sum) Lee ...

  4. Leetcode之回溯法专题-212&period; 单词搜索 II(Word Search II)

    Leetcode之回溯法专题-212. 单词搜索 II(Word Search II) 给定一个二维网格 board 和一个字典中的单词列表 words,找出所有同时在二维网格和字典中出现的单词. 单 ...

  5. Leetcode之回溯法专题-131&period; 分割回文串(Palindrome Partitioning)

    Leetcode之回溯法专题-131. 分割回文串(Palindrome Partitioning) 给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串. 返回 s 所有可能的分割方案. ...

  6. Leetcode之回溯法专题-90&period; 子集 II(Subsets II)

    Leetcode之回溯法专题-90. 子集 II(Subsets II) 给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集). 说明:解集不能包含重复的子集. 示例: 输入 ...

  7. Leetcode之回溯法专题-79&period; 单词搜索(Word Search)

    Leetcode之回溯法专题-79. 单词搜索(Word Search) 给定一个二维网格和一个单词,找出该单词是否存在于网格中. 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元 ...

  8. Leetcode之回溯法专题-78&period; 子集(Subsets)

    Leetcode之回溯法专题-78. 子集(Subsets) 给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集). 说明:解集不能包含重复的子集. 示例: 输入: nums = ...

  9. Leetcode之回溯法专题-77&period; 组合(Combinations)

    Leetcode之回溯法专题-77. 组合(Combinations)   给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合. 示例: 输入: n = 4, k = 2 输 ...

随机推荐

  1. uGUI练习 开篇

    一.准备阶段 1.Unity 4.6 Beta b18或更高版本(注:目前泄露版的Unity5.0Beta 对UI的支持并没有4.6 Beta那么好) 2.了解 Unity 2D Sprite的基础知 ...

  2. XNA Game Studio4&period;0 Programming 随便读,随便记。

    一.精灵和2D图形 1.什么是2D ? 2D可以理解为 two-Dimentionanl  , 2-dimentional 的缩写. 意就是两维的,比如 数学中的 直角坐标系 所能描述的就是一个2D的 ...

  3. c - 字符串的拼接&period;

    完整代码: #include <stdio.h> #include <string.h> #include <malloc.h> #define TRUE 1 #d ...

  4. Pyhton编程(三)之Pycharm安装及运算符

    一:上节题目解答 1)使用while循环输出 1 2 3 4 5 6 8 9 10(注意:没有7) n=1while n<11: if n==7: pass //pass代码段指代空代码.. e ...

  5. &period;net mvc 上传头像

    我用的是mvc5  开发环境vs2017 [仅供参考] [视图代码] <div > <img src="@path" alt="@att.Count&q ...

  6. python flask 如何修改默认端口号

    场景:按照github文档上启动一个flask的app,默认是用5000端口,如果5000端口被占用,启动失败. 样例代码: from flask import Flask app = Flask(_ ...

  7. 开源虚拟化KVM(一)搭建部署与概述

    一,KVM概述 1.1 虚拟化概述 在计算机技术中,虚拟化意味着创建设备或资源的虚拟版本,如服务器,存储设备,网络或者操作系统等等 [x] 虚拟化技术分类: 系统虚拟化(我们主要讨论的反向) 存储虚拟 ...

  8. Spring MVC整合Mybatis 入门

    本文记录使用Intellij创建Maven Web工程搭建Spring MVC + Mybatis 的一个非常简单的示例.关于Mybatis的入门使用可参考这篇文章,本文在该文的基础上,引入了Spri ...

  9. android 日期控件 DatePicker

    DatePicker的缺陷 提供的API太少,没办法个性化定制.比如,不能指定某部分的颜色,不能控制显示的部分等. xml中提供的属性太少,同样影响定制化. 兼容性问题太多,在4.x,5.x和6.0+ ...

  10. WEB下载显示下载名称乱码--java

    将文件名编码转换为ISO8859-1即可,如下 downloadFileName = new String(fileName.getBytes("gbk"), "ISO8 ...