About Us

Students have an amazing amount of value to offer one another, but most of that goes unrealized.

Our mission is to personalize higher education by allowing students to teach one another, in every format possible. Read our story in the main site menu.

 

    Generate Parentheses Problem

    The problem is: Given N pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

    For example, given N = 3, a solution set is:

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

    The naive solution is to generate all combinations of N pairs of parentheses, then checking if each one is valid.


    The naive solution is implemented as follows:

    A better solution is to use backtracking. Instead of generation all combinations of N pairs of parentheses, we generate valid parentheses through recursions. This can be done by keeping track of the number of opening and closing brackets.


    We can generate an opening bracket if the number of it is less than N. And we can generate a closing bracket if it is less than the number of opening brackets.


    The backtracking solution is implemented as follows:


    Book a Tutoring Session

    Eunsub Lee

    March 28, 2020

    View Profile

    Book a Tutoring Session