Generate Parantheses

Before we start solving this problem, let’s do some math first. The problem statement clearly states that we have N pairs of parentheses to work with. That means for a string to be considered as part of the solution, it must be of size 2N.

Once we have generated a string of size 2N, for it to actually be a part of the solution, we will have to check if there is a balance in the opening and closing parentheses. If these conditions are met, the string is a part of the solution.

How many strings can be generated? At every index in the string we have 2 options, i.e. either a ( or a ) and we have to make this selection 2N times, that gives us a total of 2^2N strings.

For example, with N = 3, the length of the string should be 6 and there will be 2x2x2x2x2x2 or 2^6 strings that can be generated. Once a string has been generated, it will take us O(N) time to scan the string and validate it.

This crude algorithm will give us a time complexity of O(Nx2^2N) where N comes from scanning and 2^2N comes from generating. The space complexity can be limited to O(2^2N) for holding all the generated strings.

To make this solution more efficient, we should come up with a way that allows us to check if it’s okay to add a ( or a ) and this can be done by keeping count. We know for a fact that at any given point the number of ( has to be less than or equal to N and for the string to be balanced, the number of ) has to be less than or equal to (. This is the crucial part. I messed up my initial implementation of the code by assuming that ) also has to be less than or equal to N and as a result I started generated unbalanced strings.

This is a classic backtracking problem and can be solved using recursion. The code to do this looks something like:

func generateParenthesis(_ n: Int) -> [String] {
  var result = [String]()
  var s: String = ""
  
  func backtrack(numOpen:Int = 0, numClose: Int = 0) {
    if s.count == 2 * n {
      result.append(s)
      return
    }
    
    if numOpen < n {
      s.append("(")
      backtrack(numOpen: numOpen + 1, numClose: numClose)
      s.removeLast()
    }
    
    if numClose < numOpen {
      s.append(")")
      backtrack(numOpen: numOpen, numClose: numClose + 1)
      s.removeLast()
    }
  }
  
  backtrack()
  return result
}

Time and Space Complexity: We have only generated only those strings that will be a part of the valid solution which is essentially a subset of the 2^2N elements. It turns out this is the Nth Catalan number which is basically the kind of math I am unfamiliar with! Leetcode has a not so detailed instruction on this.

Code hosted on Github.