生成括号

已知n组括号,开发一个程序,生成这n组括号所有的合法的组合可能例如:n = 3 结果为:["((())) "," (()())","()(()) "," ()()()"] LeetCode 22. Generate Parentheses

n组括号,括号字符串长度为2*n,字符串中的每个字符有两种选择可能,“(”或“)”,故有2^2n种可能。

递归生成所有可能
#include<stdio.h>
#include<vector>
#include<string>
//当item用来生成的括号字符串,n为数组,result为最终结果
void generate(std::string item, int n , std::vector<std::string> &result ){
  if( i == 2*n)){
      result.push_back(item);
      return ;
  }
  generate( item + '(',n, result );
  generate(item+')',n,result);
}
int main(){
 std::vector<std::string> result;
 generate("",2,result);
 for( int i = 0;i< result.size();i++){
    print("%s\n",result[i].c_str());
}
  return 0;
}

在组成的所有可能中,哪些是合法的? 1.左括号与右括号的数量不可超过n 。 2.每放一个左括号,才可放一个右括号,即右括号 不可先于左括号放置。 故递归需要限制条件: 1.左括号与右括号的数量,最多放置n个。 2.若左括号的数量<=右括号数量,不可进行放 置右括号的递归。

#include<string>
#include<vector>
class Solution{
public:
    std::vector<std::string> generateParenthesis(int n){
        std::vector<std::string> result;
        generate("",nun,result);
        return result;
private:
// 当前还可以放置左括号的数量left,右括号数量right。
    void generate(std::string item , int left, int right, std::vector<std::string> & result){
        if(left == 0 && right == 0){
            result.push_back(item);
            return; 
        }
        if(left > 0 ){
            generate(item+'(',left-1,right,result);
        }
        if(left < right){
            generate(item+')',left,right-1,result);
        }
    }
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

map按key和按value排序

看一个题: 查找和排序 题目:输入任意(用户,成绩)序列,可以获得成绩从高到低或从低到高的排列,相同成绩 都按先录入排列在前的规则处理。 例示: jack 70...

40230
来自专栏Golang语言社区

map按key和按value排序

看一个题: 查找和排序 题目:输入任意(用户,成绩)序列,可以获得成绩从高到低或从低到高的排列,相同成绩 都按先录入排列在前的规则处理。 例示: jack 70...

59280
来自专栏云霄雨霁

排序----选择排序

17000
来自专栏calmound

uva Andy's First Dictionary

题目很简单,数组开大就好,5000但加上重复就不够了10000都小,sort排序前闭合后开,对二维字符窜排序用结构体,所以只有一组的时候只是本身但是不会出现RE...

35240
来自专栏PHP在线

PHP生成随机密码的4种方法及性能对比

方法一: 1、在 33 – 126 中生成一个随机整数,如 35, 2、将 35 转换成对应的ASCII码字符,如 35 对应 # 3、重复以上 1、2 步骤 ...

32260
来自专栏kalifaの日々

C++构造无向图&求最短路径源码

用vector<edge> es[MAX]表示点,每个点队列里放着点的相邻边和到边的距离。 以下源码经过测试可运行 #include <iostream> #i...

33150
来自专栏Python小屋

Python从序列中选择k个不重复元素

集合中的元素不允许重复,Python集合的内部实现为此做了大量相应的优化,判断集合中是否包含某元素时比列表速度快很多。下面的代码用于返回指定范围内一定数量的不重...

36060
来自专栏开发技术

排序之冒泡排序

  本篇博客是在伍迷兄的博客基础上进行的,其博客地址点击就可以进去,里面好博客很多,我的排序算法都来自于此;一些数据结构方面的概念我就不多阐述了,伍迷兄的博客中...

9640
来自专栏Java Web

最大子段和问题

问题描述: 给定长度为n的整数序列,a[1...n], 求[1,n]某个子区间[i , j]使得a[i]+…+a[j]和最大,或者求出最大的这个和。如果该序列的...

43950
来自专栏章鱼的慢慢技术路

LeetCode_832. Flipping an Image_Solution

题目所描述的意思是对每个数组先进行取反,并且对数组中的每个元素进行取反转换,所以一共要执行两个操作。

9120

扫码关注云+社区

领取腾讯云代金券