Leetcode 22 Solution

This article provides solution to leetcode question 22 (generate-parentheses)

Tags:

Access this page by simply typing in "lcs 22" in your browser address bar if you have bunnylol configured.

Leetcode Question Link

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[0] = 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;
        }
    }
};