Generate Parentheses Problem Solution

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

Example :

Input: n = 3
Output: [“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

Generate Parentheses Problem Solution

Problem Solution In Python

def parenthesis(n,i,ans,s,op,cl):
    if cl > op or cl > n or op > n: return
    if op == n and cl == n:
        ans.append(s)
        return
    parenthesis(n,i+1,ans,s+"(",op+1,cl)
    parenthesis(n,i+1,ans,s+")",op,cl+1)  
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        parenthesis(n,0,ans,"",0,0)
        return ans

Problem Solution In Java

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> rst = new ArrayList<>();
        if (n <= 0) return rst;
        backtrack(new StringBuilder(), n, n, rst);
        return rst;
    }
    
    private void backtrack(StringBuilder sb, int left, int right, List<String> rst) {
        
        if (left == 0 && right == 0) {
            rst.add(sb.toString());
            return;
        } 
        else if (left < 0 || right < 0) return;
        else if (left > right) return;
        
        sb.append("(");
        backtrack(sb, left - 1, right, rst);
        sb.deleteCharAt(sb.length() - 1);
        sb.append(")");
        backtrack(sb, left, right - 1, rst);
        sb.deleteCharAt(sb.length() - 1);
    }
}

Problem Solution In C++

class Solution {
public:
    vector<string> res;

    void helper(vector<string> &res, string curr, int n, int left, int right) {
        if (curr.length() == n * 2 && left == right) {
            res.push_back(curr);
            return;
        }
        if (left < n) {
            curr.push_back('(');
            helper(res, curr, n, left + 1, right);
            curr.pop_back();
        }
        if (right < left) {
            curr.push_back(')');
            helper(res, curr, n, left, right + 1);
            curr.pop_back();
        }
    }

    vector<string> generateParenthesis(int n) {

        helper(res, "", n, 0, 0);
        return res;
    }
};

Problem Solution In C

int count=-1;
void func(int n,int index,char **ans,char *temp,int start,int end){
    if(start==n&&end==n){
        temp[2*n]='\0';
        ++count;
        ans[count]=(char *)malloc(sizeof(char)*((2*n)+1));
        memset(ans[count],0,sizeof(char)*((2*n)+1));
        strcpy(ans[count],temp);  
        return;
    }
    if(start<n){
        temp[index]='(';
        func(n,index+1,ans,temp,start+1,end); 
    } 
    if(start>end){
        temp[index]=')';
        func(n,index+1,ans,temp,start,end+1);
    }
}
char ** generateParenthesis(int n, int* returnSize){
    char **ans=(char **)malloc(sizeof(char *)*1500);
    memset(ans,0,sizeof(char*)*1500);
    char *temp=(char *)malloc(sizeof(char)*((2*n)+1));
    memset(temp,0,sizeof(char)*((2*n)+1));
    count=-1;
    func(n,0,ans,temp,0,0);
    *returnSize=count+1;
    free(temp);
    return ans;
}