Close

Mohit Athwani

MA

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.