Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"

Solving this recursively can lead to a good and concise code. Though DP can be used to solve it too.

1. Recursive way
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        string r;
        stack<string> st;
        dfs(res,r,0,0,n);
        return res;
    }
   
    void dfs(vector<string> &res, string r, int leftCount, int rightCount,int n)
    {
        if (leftCount==n&&rightCount==n)
        {
            res.push_back(r);
            return;
        }
        else
        {
            if (leftCount<n)
            {
                dfs(res,r+"(",leftCount+1,rightCount,n);
            }
           
            if (rightCount<leftCount)
            {
                dfs(res,r+")",leftCount,rightCount+1,n);
            }
        }
       
    }
};

2. DP