Leet code problem 22 Generate Paranthesis

sharma74542

Abhishek Sharma Gaur

Posted on November 2, 2023

Leet code problem 22 Generate Paranthesis

This code defines a class Solution with a method generateParenthesis to generate valid combinations of parentheses for a given number n. It uses a backtracking algorithm to create these combinations. Here's a breakdown of the code:

stack and element are defined as empty lists. stack will store the valid parenthesis combinations, and element will keep track of the current combination being constructed.

Inside the Solution class, there's a nested function backtrack which is used for the recursive backtracking. It takes two parameters, openN and closeN, representing the count of open and close parentheses, respectively.

The backtrack function starts by checking if the number of open parentheses (openN) is equal to n, and the number of close parentheses (closeN) is also equal to n. If this condition is met, it means a valid combination of parentheses has been formed, so it joins the elements in the element list and appends it to the stack.

If the above condition is not met, the code proceeds with two recursive calls:

If the count of open parentheses (openN) is less than n, it appends an opening parenthesis "(" to the element, increments openN, and makes a recursive call to backtrack`.
If the count of close parentheses (closeN) is less than the count of open parentheses (openN), it appends a closing parenthesis ")" to the element, increments closeN, and makes another recursive call to backtrack.
The code prints some debugging information at various points within the backtrack function.

Finally, the backtrack function is called initially with both openN and closeN set to 0 to start the process of generating valid combinations. The stack containing all the valid combinations is returned.

The code includes some commented-out example usage at the end. To use the generateParenthesis function, you should create an instance of the Solution class and call the method on that instance with the desired value of n.

Code in python
`
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
stack = []
element = []

    def backtrack(openN, closeN):
        print("openN: " + str(openN) + " closeN: " + str(closeN) + " n: " + str(n))
        if openN == n and closeN == n:
            print("First condition: ", element)
            stack.append("".join(element))
            return
        if openN < n:
            element.append("(")
            backtrack(openN + 1, closeN)
            print("Second condition: ", element)
            element.pop()
        if closeN < openN:
            element.append(")")
            backtrack(openN, closeN + 1)
            print("Third condition: ", element)
            element.pop()

    backtrack(0, 0)
    return stack
Enter fullscreen mode Exit fullscreen mode

`

Code in Javascript

`
/**

  • @param {number} n
  • @return {string[]}
    */
    var generateParenthesis = function(n) {
    let stack = []
    let element = []

    var backtrack = function(openN, closeN) {
    console.log("openN: " + openN + " closeN: " + closeN + " n: " + n);
    if(openN == n && closeN == n){
    console.log("First condition: ", element);
    stack.push(element.join(""))
    return
    }
    if(openN < n) {
    element.push("(")
    backtrack(openN+1, closeN)
    console.log("Second condition: ", element);
    element.pop()
    }
    if(closeN < openN) {
    element.push(")")
    backtrack(openN, closeN+1)
    console.log("Third condition: ", element);
    element.pop()
    }
    return
    }
    backtrack(0, 0)
    return stack
    };
    `

💖 💪 🙅 🚩
sharma74542
Abhishek Sharma Gaur

Posted on November 2, 2023

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related