22. Generate Parentheses
1. Description
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
2. Example
Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1
Output: ["()"]
3. Constraints
- 1 <= n <= 8
4. Solutions
My Accepted Solution
I don’t know its complexity, as the Leetcode says
Time complexity: O($\frac {4^n} {\sqrt{n}}$)
Space complexity: O($\frac {4^n} {\sqrt{n}}$)
class Solution {
public:
vector<string> generateParenthesis(const int n) {
string combination;
generate_combination(n, n, 0, combination);
return combinations;
}
private:
vector<string> combinations;
void generate_combination(
const int left_budget,
const int right_budget,
const int balance,
string &combination) {
if (left_budget == 0 && right_budget == 0 && balance == 0) {
combinations.emplace_back(combination);
} else if ((left_budget > 0 || right_budget > 0) && balance >= 0) {
if (left_budget > 0) {
combination.push_back('(');
generate_combination(left_budget - 1, right_budget, balance + 1, combination);
combination.pop_back();
}
if (right_budget > 0) {
combination.push_back(')');
generate_combination(left_budget, right_budget - 1, balance - 1, combination);
combination.pop_back();
}
}
}
};