標(biāo)簽（空格分隔）： C++ 算法 LeetCode 字符串 遞歸
每日算法——leetcode系列
問(wèn)題 Generate Parentheses
Difficulty: Medium
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:
<code>"((()))", "(()())", "(())()", "()(())", "()()()"</code>
class Solution {
public:
vector<string> generateParenthesis(int n) {
}
};
翻譯
括符生成
難度系數(shù)：中等
思路
此題難在要想到遞歸箩兽。
假設(shè)：左括符個(gè)數(shù)用left表示，右括符個(gè)數(shù)用right表示
遞歸終止條件： left = right = n
先要生成左括符蹬挺，可以生成左括符的條件：left < n
生成右括符條件： right < left
代碼
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
if (n > 0) {
generator(n, 0, 0, "", result);
}
return result;
}
private:
void generator(int n, int left, int right, string s, vector<string> &result) {
if (left == n && right == n) {
result.push_back(s);
return;
}
if (left < n) {
generator(n, left+1, right, s + '(', result);
}
if (right < left) {
generator(n, left, right + 1, s + ')', result);
}
}
};
