Generate Parentheses

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> out;
        string path;
        function<void(int,int)> dfs = [&](int open, int close){
            if ((int)path.size() == 2 * n) { out.push_back(path); return; }
            if (open < n) {
                path.push_back('(');
                dfs(open + 1, close);
                path.pop_back();
            }
            if (close < open) {
                path.push_back(')');
                dfs(open, close + 1);
                path.pop_back();
            }
        };
        dfs(0, 0);
        return out;
    }
};

func generateParenthesis(n int) []string {
    out := []string{}
    path := []byte{}
    var dfs func(open, close int)
    dfs = func(open, close int) {
        if len(path) == 2*n {
            out = append(out, string(path))
            return
        }
        if open < n {
            path = append(path, '(')
            dfs(open+1, close)
            path = path[:len(path)-1]
        }
        if close < open {
            path = append(path, ')')
            dfs(open, close+1)
            path = path[:len(path)-1]
        }
    }
    dfs(0, 0)
    return out
}

from typing import List

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        out: List[str] = []
        path: List[str] = []

        def dfs(open_n: int, close_n: int) -> None:
            if len(path) == 2 * n:
                out.append(''.join(path))
                return
            if open_n < n:
                path.append('(')
                dfs(open_n + 1, close_n)
                path.pop()
            if close_n < open_n:
                path.append(')')
                dfs(open_n, close_n + 1)
                path.pop()

        dfs(0, 0)
        return out

function generateParenthesis(n) {
    const out = [];
    const path = [];
    function dfs(open, close) {
        if (path.length === 2 * n) {
            out.push(path.join(''));
            return;
        }
        if (open < n) {
            path.push('(');
            dfs(open + 1, close);
            path.pop();
        }
        if (close < open) {
            path.push(')');
            dfs(open, close + 1);
            path.pop();
        }
    }
    dfs(0, 0);
    return out;
}

class Solution {
    private int n;
    private List<String> out;
    private StringBuilder path;

    public List<String> generateParenthesis(int n) {
        this.n = n;
        this.out = new ArrayList<>();
        this.path = new StringBuilder();
        dfs(0, 0);
        return out;
    }

    private void dfs(int open, int close) {
        if (path.length() == 2 * n) {
            out.add(path.toString());
            return;
        }
        if (open < n) {
            path.append('(');
            dfs(open + 1, close);
            path.deleteCharAt(path.length() - 1);
        }
        if (close < open) {
            path.append(')');
            dfs(open, close + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

function generateParenthesis(n: number): string[] {
    const out: string[] = [];
    const path: string[] = [];
    const dfs = (open: number, close: number): void => {
        if (path.length === 2 * n) {
            out.push(path.join(''));
            return;
        }
        if (open < n) {
            path.push('(');
            dfs(open + 1, close);
            path.pop();
        }
        if (close < open) {
            path.push(')');
            dfs(open, close + 1);
            path.pop();
        }
    };
    dfs(0, 0);
    return out;
}