Posted on

C++ Solution for Generate Parentheses Leetcode Problem #22

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

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Solution:

#include <string>
#include <vector>
#include <iostream>
#include <functional> // Include this for std::function

using namespace std;

vector<string> generateParenthesis(int n) {
vector<string> solutions;

// Explicitly declare the lambda with std::function
function<void(string, int, int)> backtrack = [&](const string& current, int open, int close) {
if (current.length() == n * 2) {
solutions.push_back(current);
return;
}
if (open < n) {
backtrack(current + '(', open + 1, close);
}
if (close < open) {
backtrack(current + ')', open, close + 1);
}
};

// Start the backtracking
backtrack("", 0, 0);

return solutions;
}

// Main function
int main() {
int n = 3; // Example input
vector<string> result = generateParenthesis(n);
cout << "Number of solutions: " << result.size() << endl;
// Print the results
for (const auto &str: result) {
cout << str << endl;
}

return 0;
}

Main Takeaways

You have to start with an open parentheses. So the logic reads to add open parentheses until all of them are exhausted. Then you actually start backtracking and adding a closing parentheses. So for n=2 you get a simple tree like this one below. Watch the video if you need more understanding on how to solve this one.

      o
     /
    /
   (
  / \
 /   \
((    ()
 |    |
(()) ()()