Easy to understand but maybe prolong java solution


  • -1
    W

    public class Solution {
    public List<String> generateParenthesis(int n) {
    char[] helper = new char[2n];
    for(int i=0; i<n;i++)
    helper[i]='(';
    for(int i=n; i<2
    n; i++)
    helper[i]=')';

        boolean marked[] = new boolean[2*n];
        for(int i=0; i<2*n; i++)
        marked[i] =false;
        
        int on =1; //open parentheses number
        int cn=0; // close parenthese number
        
        List<String> ans = new ArrayList();
        String s ="(";
        marked[0]=true;
        
        helper(ans, s, helper, marked, on, cn, n);
        return ans;
    }
    
    
    private void helper(List<String> ans, String s, char[] helper, boolean[] marked, int on, int cn, int n){
        if(s.length()==2*n){
         String temp =s;    
         ans.add(temp);
         return;
        }
        
        for(int i=1; i<2*n; i++){
           if(helper[i]==helper[i-1]){//attepting to add i;
               if(marked[i-1]==true && marked[i]==false &&( (helper[i]=='(') ||( helper[i]==')'&& on>cn)) ){
                   s=s+helper[i];
                   marked[i]=true;
                   if(helper[i]=='(') on++;
                   else cn++;
                   helper(ans, s, helper, marked, on, cn, n);   
                   s=s.substring(0,s.length()-1);
                   marked[i]=false;
                   if(helper[i]=='(') on--;
                   else cn--;
               }
           } else{
               if(marked[i]==false && on>cn){
                   s=s+helper[i];
                   marked[i]=true;
                   cn++;
                   helper(ans, s, helper, marked, on, cn, n); 
                   s=s.substring(0,s.length()-1);
                   marked[i]=false;
                   cn--;
               }
           }
           
           
        }
      
      
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.