Generate Parentheses In C,CPP,JAVA,PYTHON,C#,JS

/ DSA / By
Spread the love
A close-up shot of a person coding on a laptop, focusing on the hands and screen.

The problem of Generating Parentheses is to find all combinations of well-formed parentheses given n pairs of parentheses. A well-formed parentheses sequence is a string consisting of n pairs of parentheses where each opening parenthesis ( is closed by a corresponding closing parenthesis ).

Problem Statement:

Given n, generate all combinations of well-formed parentheses that can be made using n pairs of parentheses.

Example:

Input:

  • n = 3

Output:

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

Explanation: For n = 3, there are 5 possible combinations of valid parentheses.

Approach:

To generate all valid parentheses combinations, we can use Backtracking. The idea is to keep track of the number of opening ( and closing ) parentheses used so far. We can add an opening parenthesis if we have not yet used n opening parentheses, and we can add a closing parenthesis if the number of closing parentheses used is less than the number of opening parentheses used.

  1. Base Case: When both the number of opening and closing parentheses used is equal to n, we have a valid combination of parentheses.
  2. Recursive Case:
    • If we have not yet used n opening parentheses, we can add an opening parenthesis.
    • If the number of closing parentheses used is less than the number of opening parentheses, we can add a closing parenthesis.
  3. Backtracking: The algorithm explores all possible valid configurations and backtracks when necessary.

Time Complexity:

  • Time complexity: The number of valid combinations is Catalan number C(n). The total number of operations is proportional to C(n). Each valid sequence takes O(n) time to generate, so the total time complexity is O(4^n / √n).
  • Space complexity: We need space for the recursion stack and storing the valid parentheses sequences. The space complexity is O(n) for the recursion and O(C(n)) for storing the results.

Algorithm:

  1. Initialize an empty list to store the results.
  2. Define a recursive function that takes the current string of parentheses, the number of opening parentheses used, and the number of closing parentheses used.
  3. Recursively build valid parentheses strings by adding ( or ) based on the current state.
  4. When a valid string is found (i.e., both opening and closing parentheses used equals n), add it to the result list.
  5. Return the result list.

Code Implementation in Different Languages:

1. C

#include <stdio.h>
#include <string.h>

void generateParentheses(int n, int open, int close, char *current, char **result, int *resultIndex) {
    if (open == n && close == n) {
        result[*resultIndex] = strdup(current);
        (*resultIndex)++;
        return;
    }
    
    if (open < n) {
        current[strlen(current)] = '(';
        generateParentheses(n, open + 1, close, current, result, resultIndex);
        current[strlen(current) - 1] = '\0';
    }
    
    if (close < open) {
        current[strlen(current)] = ')';
        generateParentheses(n, open, close + 1, current, result, resultIndex);
        current[strlen(current) - 1] = '\0';
    }
}

char** generateParenthesis(int n, int *returnSize) {
    char **result = (char **)malloc(sizeof(char*) * 1000);
    *returnSize = 0;
    
    char current[2 * n + 1];
    current[0] = '\0';
    
    generateParentheses(n, 0, 0, current, result, returnSize);
    
    return result;
}

int main() {
    int n = 3;
    int returnSize = 0;
    char **result = generateParenthesis(n, &returnSize);
    
    for (int i = 0; i < returnSize; i++) {
        printf("%s\n", result[i]);
    }
    
    return 0;
}

2. C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

void generateParentheses(int n, int open, int close, string &current, vector<string> &result) {
    if (open == n && close == n) {
        result.push_back(current);
        return;
    }

    if (open < n) {
        current.push_back('(');
        generateParentheses(n, open + 1, close, current, result);
        current.pop_back();
    }

    if (close < open) {
        current.push_back(')');
        generateParentheses(n, open, close + 1, current, result);
        current.pop_back();
    }
}

vector<string> generateParenthesis(int n) {
    vector<string> result;
    string current;
    generateParentheses(n, 0, 0, current, result);
    return result;
}

int main() {
    int n = 3;
    vector<string> result = generateParenthesis(n);
    for (const string &str : result) {
        cout << str << endl;
    }
    return 0;
}

3. Java

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public void generateParentheses(int n, int open, int close, String current, List<String> result) {
        if (open == n && close == n) {
            result.add(current);
            return;
        }

        if (open < n) {
            generateParentheses(n, open + 1, close, current + "(", result);
        }

        if (close < open) {
            generateParentheses(n, open, close + 1, current + ")", result);
        }
    }

    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        generateParentheses(n, 0, 0, "", result);
        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<String> result = solution.generateParenthesis(3);
        for (String s : result) {
            System.out.println(s);
        }
    }
}

4. Python

def generateParentheses(n: int):
    result = []
    
    def backtrack(current, open, close):
        if open == n and close == n:
            result.append(current)
            return
        
        if open < n:
            backtrack(current + '(', open + 1, close)
        
        if close < open:
            backtrack(current + ')', open, close + 1)
    
    backtrack("", 0, 0)
    return result

# Test the function
print(generateParentheses(3))

5. C#

using System;
using System.Collections.Generic;

public class Solution {
    public void GenerateParentheses(int n, int open, int close, string current, List<string> result) {
        if (open == n && close == n) {
            result.Add(current);
            return;
        }

        if (open < n) {
            GenerateParentheses(n, open + 1, close, current + "(", result);
        }

        if (close < open) {
            GenerateParentheses(n, open, close + 1, current + ")", result);
        }
    }

    public List<string> GenerateParenthesis(int n) {
        List<string> result = new List<string>();
        GenerateParentheses(n, 0, 0, "", result);
        return result;
    }

    public static void Main() {
        Solution solution = new Solution();
        List<string> result = solution.GenerateParenthesis(3);
        foreach (string s in result) {
            Console.WriteLine(s);
        }
    }
}

6. JavaScript

var generateParenthesis = function(n) {
    const result = [];
    
    function backtrack(current, open, close) {
        if (open === n && close === n) {
            result.push(current);
            return;
        }
        
        if (open < n) {
            backtrack(current + '(', open + 1, close);
        }
        
        if (close < open) {
            backtrack(current + ')', open, close + 1);
        }
    }

    backtrack("", 0, 0);
    return result;
};

// Test the function
console.log(generateParenthesis(3));

Conclusion:

  • Backtracking is the key technique for solving the “Generate Parentheses” problem.
  • By maintaining counts of the open and close parentheses, we can ensure that the generated strings are valid without needing to check them post-generation.
  • The time complexity is O(4^n / √n) due to the number of valid parentheses sequences.