022 Generate Parentheses[M]

1 題目描述

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

難度：Medium

2 題目樣例

For example, given n = 3, a solution set is:[ "((()))", "(()())", "(())()", "()(())", "()()()"]

3 題意分析

給出一個數字n，要求返回含有n對括弧的，所有合法的括弧序列。

（這裡的合法，大家看看樣例就知道是什麼意思了......理解就好。）

4 思路分析

嘻嘻，我覺得這個題目比上一個簡單欸！！

我們可以利用深度優先搜索的思想，用遞歸的方法來解決這個問題。

每次左括弧多於右括弧時，可以加左括弧或者右括弧。

如果左括弧等於右括弧，就只能加左括弧。

左括弧達到數量上限，只能加右括弧。右括弧同理。

代碼實現如下：

class Solution { public: void generate(int left, int right, string str, vector<string>& res) { if(left == 0 && right == 0) { res.push_back(str); return; } if(left > 0) { generate(left - 1, right, str + (, res); } if(right > left) { generate(left, right - 1, str + ), res); } } vector<string> generateParenthesis(int n) { vector<string> res; generate(n, n, "", res); return res; } };

這道題目所有的提交代碼的用時都相當短。我上邊的這段代碼用時3ms，但卻落在了後10%的區間里。我看了看其他區間的代碼，基本上也和上邊的一個樣。至於為什麼時間用的比較短嘛...玄學，玄學。

5 後記

外邊的煙花聲吵得我難以繼續寫下去了...

我永遠愛摸魚.jpg

推薦閱讀：