Generate Parentheses

class Solution {
public:
    std::vector<std::string> createParentheses(int count) {
        if (count == 0) {
            return std::vector<std::string>{""};
        }
        std::vector<std::string> result;
        for (int lc = 0; lc < count; ++lc) {
            for (std::string lPart : createParentheses(lc)) {
                for (std::string rPart : createParentheses(count - 1 - lc)) {
                    result.push_back("(" + lPart + ")" + rPart);
                }
            }
        }
        return result;
    }
};

The provided C++ code defines a class named Solution which includes a method called createParentheses. This method generates all valid combinations of count pairs of parentheses.

Explanation of the Implementation:

• The method createParentheses takes an integer count which specifies the number of pairs of parentheses.
• It starts with a base case: if count is 0, it returns a vector containing an empty string. This represents the base scenario where no parentheses are needed.
• For generating combinations, the method uses a recursive approach:
  • It initializes an empty vector of strings named result to store the combinations of parentheses.
  • It iterates through possible splits of the count using a variable lc, where lc indicates the number of left parentheses.
  • Inside the outer loop, it calls itself recursively to generate the left part of the parentheses string (lPart) using lc as the argument.
  • It then calls itself again to generate the right part of the parentheses string (rPart), using count - 1 - lc as the argument.
  • For each pair of left and right parts obtained from recursive calls, the method constructs a valid set of parentheses by wrapping lPart in a single pair of parentheses and then concatenating it with rPart. This constructed string is then added to the result vector.
• Finally, after iterating through all possibilities, the result vector containing all valid combinations of parentheses is returned.

How to Utilize This Method:

• Create an instance of the Solution class.
• Call the createParentheses method with a specific number of pairs of parentheses you wish to generate.
• The method returns a vector of strings, where each string represents a valid permutation of the parentheses.

class Solution {
    public List<String> generateBalancedParenthesis(int count) {
        if (count == 0) {
            return new ArrayList(Arrays.asList(""));
        }

        List<String> result = new ArrayList();
        for (
            int openBrace = 0;
            openBrace < count;
            ++openBrace
        ) for (String leftPart : generateBalancedParenthesis(
            openBrace
        )) for (String rightPart : generateBalancedParenthesis(
            count - 1 - openBrace
        )) result.add("(" + leftPart + ")" + rightPart);
        return result;
    }
}

The given Java solution is designed to generate all combinations of well-formed parentheses for a given number count. Here are the core components and the functionality of the code:

• The generateBalancedParenthesis(int count) method is part of a Solution class. It uses recursion to create all possible combinations of balanced parentheses.

• An ArrayList named result is created to store the combinations.

• If count is 0, the method returns an ArrayList with an empty string. This represents the base case of the recursion, indicating there are no more parentheses to balance.

• For the non-base cases, the method iterates through possible splits between the left and right parts of the parentheses string. It makes a recursive call for each possible number of opening braces openBrace and combines the results.

• The loop combines the left and right parts of the parentheses: for each combination from the recursive call, it adds an opening parenthesis ( then the leftPart, a closing parenthesis ), and then the rightPart.

• Finally, the method returns the result list containing all possible well-formed parentheses combinations.

For example, when count is 3, some of the strings returned would be ((())), (()()), (())(), ()(()), and ()()().

This approach ensures that all potential combinations are covered by exploring every possible distribution of balanced pairs of parentheses through recursion, guaranteeing the correct format and balance for each combination before adding it to the result list.

char **generateCombinations(int count, int *sizeOut) {
    if (count == 0) {
        char **output = malloc(sizeof(char *));
        output[0] = malloc(sizeof(char));
        output[0][0] = '\0';
        *sizeOut = 1;
        return output;
    }
    int totalSize = 0, currIndex = 0;
    char **combinations = NULL;
    for (int parLeft = 0; parLeft < count; ++parLeft) {
        int countLeft = 0;
        int countRight = 0;
        char **leftParts = generateCombinations(parLeft, &countLeft);
        char **rightParts =
            generateCombinations(count - 1 - parLeft, &countRight);
        for (int i = 0; i < countLeft; ++i) {
            for (int j = 0; j < countRight; ++j) {
                totalSize +=
                    2 + strlen(leftParts[i]) + strlen(rightParts[j]);
                combinations = realloc(combinations, totalSize * sizeof(char *));
                combinations[currIndex] = malloc(2 + strlen(leftParts[i]) +
                                               strlen(rightParts[j]) + 1);
                sprintf(combinations[currIndex], "(%s)%s", leftParts[i],
                        rightParts[j]);
                ++currIndex;
            }
        }
        for (int i = 0; i < countLeft; ++i) free(leftParts[i]);
        free(leftParts);
        for (int j = 0; j < countRight; ++j) free(rightParts[j]);
        free(rightParts);
    }
    *sizeOut = currIndex;
    return combinations;
}

The solution provided is a C program that generates all possible valid parentheses combinations for a given number of pairs count. The function generateCombinations utilizes recursion and dynamic memory allocation to construct each combination.

Here's a breakdown of how the solution works:

• The function accepts an integer count, representing the number of pairs of parentheses, and a pointer sizeOut to store the total number of combinations generated.
• If count is zero (base case), the function initializes an output array with an empty string and sets sizeOut to 1.
• Two integer variables totalSize and currIndex track the total size of the combinations array and the current index, respectively.
• The function iterates through all possible splits of parentheses pairs, recursively generating combinations for the left part (parLeft) and the right part (count - 1 - parLeft).
• For each left and right combination, the function concatenates them into new strings surrounded by a pair of parentheses and stores them in the combinations array, adjusting memory allocation accordingly.
• Memory allocated for individual parts is freed after adding the new combination to avoid memory leaks.
• Finally, the function updates *sizeOut with the count of unique combinations generated, returning the combinations array.

This efficient recursive approach ensures all combinations of valid parentheses are generated properly, respecting scoping rules by ensuring each left parenthesis has a corresponding right parenthesis. Memory management is crucial, as all dynamically allocated space is properly cleaned up to prevent memory leaks.

var makeParentheses = function (count) {
    if (count === 0) {
        return [""];
    }
    let result = [];
    for (let i = 0; i < count; ++i) {
        for (let left of makeParentheses(i)) {
            for (let right of makeParentheses(count - 1 - i)) {
                result.push("(" + left + ")" + right);
            }
        }
    }
    return result;
};

The function makeParentheses effectively generates all possible combinations of well-formed parentheses given a specific number count representing pairs of parentheses. Implement this solution in JavaScript using a recursive approach.

• Define a recursive function named makeParentheses which accepts an integer count.
• Use a base case to return a list containing an empty string if count is 0, indicating no parentheses are needed.
• Initialize an empty list result to store the combinations of valid parentheses.
• Use a loop to iterate through integer values from 0 up to count.
• For each iteration, recursively invoke makeParentheses for the left part for each valid left parentheses combination and the remaining right part for each valid right parentheses combination.
• Concatenate the left and right combinations in the format ("(" + left + ")" + right) to ensure the parentheses are validly nested, and append this to the result list.
• Finally, return the result list containing all the valid combinations.

This approach ensures that for each position in the sequence, a valid configuration of nested parentheses is created, leveraging the recursive structure to explore every possible valid configuration and storing them efficiently.

class Solution:
    def generateBrackets(self, count: int) -> List[str]:
        if count == 0:
            return [""]

        results = []
        for open_count in range(count):
            for open_bracket_set in self.generateBrackets(open_count):
                for close_bracket_set in self.generateBrackets(
                    count - 1 - open_count
                ):
                    results.append("(" + open_bracket_set + ")" + close_bracket_set)

        return results

This Python solution effectively generates all possible combinations of well-formed parentheses given a number. The function generateBrackets uses recursion to build these combinations, forming the key algorithmic approach that ensures every generated string of parentheses is well-formed.

The base case of the recursion addresses situations where no parentheses are needed, simply returning a list containing an empty string. For cases where count is greater than zero, the program iteratively builds the combinations:

• Iteratively increment the number of opening brackets.
• Recursively call generateBrackets for subsets of the count, ensuring different configurations of open and closed brackets are considered.
• Concatenate the results in the form "(open_bracket_set)close_bracket_set" to maintain proper nesting and balance of the parentheses.

By iterating over all possible counts of opening brackets and recursively solving for each configuration, this solution efficiently constructs each unique sequence of well-formed parentheses, accumulating them into the results list which is returned at the end. This approach ensures comprehensive coverage of all potential combinations, leveraging recursion effectively for combinatorial generation.