Meta — Generate Parentheses (Backtracking)

n = 3 → ["((()))","(()())","(())()","()(())","()()()"]

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

function generateParenthesis(n) {
    const res = [];
    const bt = (s, o, c) => {
        if (s.length === 2*n) { res.push(s); return; }
        if (o < n) bt(s+'(', o+1, c);
        if (c < o) bt(s+')', o, c+1);
    };
    bt('', 0, 0);
    return res;
}

import java.util.*;
public List<String> generateParenthesis(int n) {
    List<String> res = new ArrayList<>();
    dfs(res, "", 0, 0, n); return res;
}
void dfs(List<String> res, String s, int o, int c, int n) {
    if (s.length()==2*n){res.add(s);return;}
    if (o<n) dfs(res,s+"(",o+1,c,n);
    if (c<o) dfs(res,s+")",o,c+1,n);
}

#include <vector>
#include <string>
using namespace std;
vector<string> generateParenthesis(int n) {
    vector<string> res;
    function<void(string,int,int)> bt=[&](string s,int o,int c){
        if((int)s.size()==2*n){res.push_back(s);return;}
        if(o<n) bt(s+"(",o+1,c);
        if(c<o) bt(s+")",o,c+1);
    };
    bt("",0,0); return res;
}

#include <string.h>
char results[1000][50]; int total=0;
void bt(char* buf, int pos, int o, int c, int n) {
    if(pos==2*n){strcpy(results[total++],buf);return;}
    if(o<n){buf[pos]='(';bt(buf,pos+1,o+1,c,n);}
    if(c<o){buf[pos]=')';bt(buf,pos+1,o,c+1,n);}
}