Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

&nbsp;
Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1
Output: ["()"]

&nbsp;
Constraints:


	1 &lt;= n &lt;= 8


class Solution:
    def generateParenthesis(self, n: int) -> list[str]:

        # Initialize the result
        res = []

        # Recursively go through all possible combinations
        def add(open, close, partialRes):

            nonlocal res

            # If we have added opening and closing parentheses n times, we reaches a solution
            if open == close == n:
                res.append("".join(partialRes))
                return

            # Add a closing parenthesis to the partial result if we have at least 1 opening parenthesis
            if close < open:
                add(open, close + 1, partialRes + [")"])

            # Add an opening parenthesis to the partial result if we haven't added n parenthesis yet
            if open < n:
                add(open + 1, close, partialRes + ["("])

        add(0, 0, [])

        return res
class Solution {
    List<String> s = new ArrayList<>();
    public void get(int n, int x, String p)
    {
        if(n==0 && x==0)
        {
            s.add(p);
            return;
        }
        if(n==0)
        {
            get(n,x-1,p+")");
        }
        else if(x==0)
        {
            get(n-1,x+1,p+"(");
        }
        else
        {
            get(n,x-1,p+")");
            get(n-1,x+1,p+"(");
        }
    }
    public List<String> generateParenthesis(int n) 
    {
        s.clear();
        get(n,0,"");
        return s;
    }
}
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        
        generate(ans,"",n,n);
        
        return ans;
    }
    
    void generate(vector<string> &ans,string s,int open,int close)
    {
        if(open == 0 && close == 0)
        {
            ans.push_back(s);
            return ;
        }
        
        if(open > 0)
        {
            generate(ans,s+'(',open-1,close);
        }
        
        if(open < close)
        {
            generate(ans,s+')',open,close-1);
        }
    }
};
var generateParenthesis = function(n) {
    let ans = []
    generate_parenthisis(n, 0, 0, "")
    return ans

    function generate_parenthisis(n, open, close, res){

        if(open==n && close == n){
            ans.push(res)
            return
        }

        if(open<n){
            generate_parenthisis(n, open+1, close, res + "(")
        }

        if(close<open){
            generate_parenthisis(n, open, close+1, res+")")
        }

    }
};
Generate Parentheses