same as LC.22. Generate Parentheses

https://leetcode.com/problems/generate-parentheses/description/

Given N pairs of parentheses “()”, return a list with all the valid permutations.

Assumptions

N >= 0

Examples

N = 1, all valid permutations are ["()"]

N = 3, all valid permutations are ["((()))", "(()())", "(())()", "()(())", "()()()"]

N = 0, all valid permutations are [""]

 

public class Solution {  public List
     
       validParentheses(int n) {    // Write your solution here.    //assume n>=0    List
      
        res = new ArrayList<>() ;    StringBuilder sol = new StringBuilder() ;    dfs(n, res, 0, 0, sol) ;    return res ;  } /*    n stores total number of "pair of ()" need to add.    So total levels == 2*n    1 stores the number of left parenthesis "(" added so far    r stores the number of right parenthesis ")" added so far    sol: solution so far */  private void dfs(int n, List
       
         res, int l , int r , StringBuilder sol){     //base case: reach the leaf and its valid value, go back    if (n == l && l == r ) {        //always deep copy, be very careful        res.add(sol.toString());        return ;    }    //case 1: add ( on this level :    //think n as the length of array, l as index    if (n > l) {        dfs(n, res, l+1 , r , sol.append("(")) ;        //remove        sol.deleteCharAt(sol.length()-1) ;    }    //case 2: add )    if (n > r && l > r ) {        dfs(n, res, l, r+1, sol.append(")")) ;        //remove        sol.deleteCharAt(sol.length()-1) ;    }  }}