Generate Parentheses: Valid Combinations Backtracking

def generateParenthesis(n):
    result = []
    def bt(s, open, close):
        if len(s) == 2 * n:
            result.append(s)
            return
        if open < n:
            bt(s + '(', open + 1, close)
        if close < open:
            bt(s + ')', open, close + 1)
    bt('', 0, 0)
    return result

print(generateParenthesis(3))
# ['((()))', '(()())', '(())()', '()(())', '()()()']

# Count: Catalan number C(n) = C(2n,n)/(n+1)
import math
def catalan(n): return math.comb(2*n, n) // (n+1)
print(catalan(3))  # 5

#include <bits/stdc++.h>
using namespace std;

vector<string> generateParenthesis(int n) {
    vector<string> result;
    function<void(string, int, int)> bt = [&](string s, int open, int close) {
        if ((int)s.size() == 2 * n) { result.push_back(s); return; }
        if (open < n) bt(s + '(', open + 1, close);
        if (close < open) bt(s + ')', open, close + 1);
    };
    bt("", 0, 0);
    return result;
}

import java.util.*;

public class GenerateParentheses {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, new StringBuilder(), 0, 0, n);
        return result;
    }

    void backtrack(List<String> result, StringBuilder sb, int open, int close, int n) {
        if (sb.length() == 2 * n) { result.add(sb.toString()); return; }
        if (open < n) {
            sb.append('(');
            backtrack(result, sb, open+1, close, n);
            sb.deleteCharAt(sb.length()-1);
        }
        if (close < open) {
            sb.append(')');
            backtrack(result, sb, open, close+1, n);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}