← Recursion

Generate Parentheses

Medium
Python
def generate_parenthesis(n):
    result=[]
    def backtrack(s,open,close):
        if len(s)==2*n: result.append(s); return
        if open<n: backtrack(s+'(',open+1,close)
        if close<open: backtrack(s+')',open,close+1)
    backtrack('',0,0)
    return result
Java
public List<String> generateParenthesis(int n){
    List<String> res=new ArrayList<>();
    backtrack(res,"",0,0,n);
    return res;
}
void backtrack(List<String> res,String s,int open,int close,int n){
    if(s.length()==2*n){res.add(s);return;}
    if(open<n) backtrack(res,s+"(",open+1,close,n);
    if(close<open) backtrack(res,s+")",open,close+1,n);
}

Key Insight

Python nested function captures result. Java passes it as parameter.

Python → Java Differences

  • Nested function captures result
  • Java passes list as parameter
  • Backtracking logic identical
Python
def generate_parenthesis(n):
    result=[]
    def backtrack(s,open,close):
        if len(s)==2*n: result.append(s); return
        if open<n: backtrack(s+'(',open+1,close)
        if close<open: backtrack(s+')',open,close+1)
    backtrack('',0,0)
    return result
Java
public List<String> generateParenthesis(int n){
    List<String> res=new ArrayList<>();
    backtrack(res,"",0,0,n);
    return res;
}
void backtrack(List<String> res,String s,int open,int close,int n){
    if(s.length()==2*n){res.add(s);return;}
    if(open<n) backtrack(res,s+"(",open+1,close,n);
    if(close<open) backtrack(res,s+")",open,close+1,n);
}

Algorithm Steps

1. Track open and close counts
2. Add ( if open<n
3. Add ) if close<open
← Previous All Recursion Next →