22. 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:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        if(n < 1)   return {};

        vector<string>  res;
        dfs(n, "", 0, 0, res);
        return res;
    }
private:
    void dfs(int num, string sol, int l, int r, vector<string>  &ret){
        if(l == num){
            sol += string(l-r, ')');
            ret.push_back(sol);
            return;
        }

        dfs(num, sol + "(" , l + 1, r, ret);

        if(l > r)   dfs(num, sol + ")", l, r + 1, ret);
    }
};