## [Leetcode]22. Generate Parentheses(C++)

### 题目描述

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: [ `"((()))"`, `"(()())"`, `"(())()"`, `"()(())"`, `"()()()"` ]

### 解题思路

• 如果 `n_left == n_right == n` 当前字符串加入结果中
• `n_left < n_right`：当前字符串不合法退出
• `n_left < n`：当前字符串添加 `(`， 递归重复上述操作
• `n_right < n`：当前字符串添加 `)`，递归重复上述操作

``````#include <vector>
#include <string>

class Solution {
public:
std::vector<std::string> generateParenthesis(int n) {
std::vector<std::string> result;
std::string current_str = "";
dfs(current_str, result, n, 0, 0);
return result;
}

private:
void dfs(std::string& current_str, std::vector<std::string>& result, int n, int n_left, int n_right) {
if (n_left == n && n_right == n) {
result.push_back(current_str);
return;
}
if (n_left < n_right) {
return;
}

if (n_left < n) {
current_str += '(';
dfs(current_str, result, n, n_left + 1, n_right);
current_str.pop_back();
}

if (n_right < n) {
current_str += ')';
dfs(current_str, result, n, n_left, n_right + 1);
current_str.pop_back();
}
}
};
``````
• 时间复杂度: O(2 ^ n)
• 空间复杂度: O(n)

GitHub 代码同步地址： 22.GenerateParentheses.cpp

Built with Hugo
Theme Stack designed by Jimmy