leetcode【第三周】:输出圆括号

    xiaoxiao2021-03-25  59

    问题描述:

    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: vector generateParenthesis(int n) { vector result; deepConstruct(n,n,"",result); return result; } void deepConstruct(int left,int right,string out,vector &result){ if(left==0&&right==0){ result.push_back(out); return; } if(left>right){ return; } if(left<=right){ if(left>0) deepConstruct(left-1,right,out+"(",result); if(right>0) deepConstruct(left,right-1,out+")",result); } } };

    时间:3ms(完全无法理解前面的那些再短时间的是如何做到的,也许考虑下不适用递归)

    转载请注明原文地址: https://ju.6miu.com/read-33529.html

    最新回复(0)