3.Generate Parentheses

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: (Recursion)

class Solution
{
public:
    void generateParenthesis(int n, vector<char> &ch, int idx, int open, int close, vector<string> &v)
    {
        if (idx == 2*n)
        {
            string s = "";
            for (int i = 0; i < ch.size(); i++)
            {
                s = s + ch[i];
            }
            v.push_back(s);
            return;
        }

        if (open < n)
        {
            ch[idx] = '(';
            generateParenthesis(n, ch, idx + 1, open + 1, close, v);
        }

        if (close < open)
        {
            ch[idx] = ')';
            generateParenthesis(n, ch, idx + 1, open, close + 1, v);
        }

        return;
    }

    vector<string> generateParenthesis(int n)
    {
        vector<string> v;
        vector<char> ch(2 * n);
        generateParenthesis(n, ch, 0, 0, 0, v);
        return v;
    }
};

Time Complexity: O(N * 2^N)