# Leetcode 22 Solution

https://leetcode.com/problems/generate-parentheses

## Thinking Process

To generate all the combinations, we think about DFS. Build up this mapping if you haven’t.

Assuming `F(n)` returns all the possible parenthesis combinations for `n` parenthesis.

• Apparently, `F(0)` returns `[""]`.
• `F(n)` can be composed by one of the following situations:
• A `1` parenthesis string, and a `n - 1` parenthesis string.
• A `2` parenthesis string, and a `n - 2` parenthesis string.
• A `3` parenthesis string, and a `n - 3` parenthesis string.

We can implement the algorithm based on the above algorithm. Just be sure to memorize your result, so that you don’t calculate any `F(n)` twice.

## Time & Space Complexity

The number of combinations is actually the catalan number.

• Time complexity: `< O(2^n)`
• Space complexity: `< O(2^n)`

NOTE: The above bound is a very loose one. A tighter bound can be found here.

## Solution

``````class Solution {
map<int, vector<string>> cache;

public:
vector<string> generateParenthesis(int n) {
auto res = vector<string>();

if (cache.find(n) != cache.end())
{
return cache[n];
}

if (n == 0)
{
res.push_back("");
cache = res;
return res;
}
else
{
for (int i = 0; i < n; i++)
{
auto a = generateParenthesis(i);
auto b = generateParenthesis(n - 1 - i);

for (auto it1 = a.begin(); it1 < a.end(); it1++)
{
for (auto it2 = b.begin(); it2 < b.end(); it2++)
{
res.push_back("(" + *it1 + ")" + *it2);
}
}
}

cache[n] = res;
return res;
}
}
};
``````