Generate All Valid Parentheses - Backtracking / Additional States

Problems
21

Here’s another way without the need to independently add individual quotes:

func dfs(n int, path []string) []string {
    if n == 1 {
        return append(path, "()")
    }

    subPaths := dfs(n-1, []string{})
    
    for i := range subPaths {
        externalParen := "(" + subPaths[i] + ")"
        preParen := "()" + subPaths[i]
        postParen := subPaths[i] + "()"
        path = append(path, externalParen)
        path = append(path, preParen )
        if preParen != postParen {
            path = append(path, postParen)
        }
    }

    return path
}

func generateParentheses(n int) []string {
    if n == 0 {
        return []string{""}
    }

    return dfs(n, []string{})
}
22

Is the space complexity really O(4^n * n) as stack only gets 2*n + 1 deep. We need space to store “all” the 2n strings that gets generated but 4^n doesn’t seem right to me. Any thoughts or clarity on this is appreciated.

23

What is the time complexity of the above solution . It is bit tricky to understand over here . In case of DFS it is easy to understand the TC .

24

My variation for solving this code:
def generate_parentheses(n: int) → List[str]:
# WRITE YOUR BRILLIANT CODE HERE
def dfs(res, path, opened, closed):
if opened == n:
res.append(‘’.join(path) + “)”*(opened-closed)) # close the rest
return
if (closed < opened):
dfs(res, path + [“)”], opened, closed+1)
if(opened < n):
dfs(res, path + [“(”], opened+1, closed)
res =
dfs(res, , 0, 0)
return res