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;
}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment