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 .