LeetCode 22. Generate Parentheses

December 25, 2024

Here's another backtracking problem. For this post, I'd like to discuss the differences between my solution and another submitted solution.

My Solution

1class Solution:
2    def generateParenthesis(self, n: int) -> List[str]:
3        results = []
4        def backtrack(openP, closedP, curr):
5            if openP == n and closedP == n:
6                results.append(''.join(curr))
7                return
8            
9            if openP != n:
10                curr.append('(')
11                backtrack(openP + 1, closedP, curr)
12                curr.pop()
13
14            if closedP < openP:
15                curr.append(')')
16                backtrack(openP, closedP + 1, curr)
17                curr.pop()
18
19        backtrack(0, 0, [])
20        return results

The time complexity is O(2n * Catalan(n)) since for each solution (there are Catalan(n)) of the recursion stack, we work on N-i subproblems, where i is from 0 to k. The space complexity is O(k * n choose k) since each result requires k space.

niits' Solution

1class Solution:
2    def generateParenthesis(self, n: int) -> List[str]:
3        res = []
4
5        def dfs(openP, closeP, s):
6            if openP == closeP and openP + closeP == n * 2:
7                res.append(s)
8                return
9            
10            if openP < n:
11                dfs(openP + 1, closeP, s + "(")
12            
13            if closeP < openP:
14                dfs(openP, closeP + 1, s + ")")
15
16        dfs(0, 0, "")
17
18        return res

The main differences I see are the base case and use of string concatanation. I believe there is marginal difference in time complexity for my equality checks and niits' addition plus multiplication equality. My solution is more readable. The use of string concatanation by niits' is easier to read, but it uses more memory as each recursive call creates a new string while mine is passed between each recursive call. The duplication of strings by recursive calls adds an average of 2n complexity to the existing 2n complexity found in my solution.

LeetCode 77. Combinations

LeetCode 207. Course Schedule