Simple ruby solution with recursion


  • 0
    C

    This code follows your thought process when you are asked to generate the answer manually by writing it down on a piece of paper. We keep appending parenthesis following two main rules. For each parenthesis that we want to insert we check if

    1. we have utilized all the open parenthesis (= n). If we have, we continue by only appending ')' to our solution.
    2. if we haven't then
      1) if each '(' is matched with a ')' , we continue by appending a '('. We cannot add a ')' here as that would break the valid parenthesis rule.
      2) if not, we have the option to add either a '(' or ')'. We follow through by appending each of the options and continuing towards generating the result.

    Finally, we have a valid result when we have utilized all the ')' . We save the result and return.
    Below is the code.

    def generate_parenthesis(n)
      result = []
      insert_p(result,'', n, 0, 0)
      result
    end
    
    
    def insert_p(res, ele, n, num_open_p, num_closed_p)
      if num_closed_p == n
        res.push(ele)
        return
      end
      if (num_open_p == n)
        insert_p(res, ele + ')', n, num_open_p, num_closed_p+1)
      else
        if (num_open_p == num_closed_p)
          insert_p(res, ele + '(', n, num_open_p+1, num_closed_p)
        else
          insert_p(res, ele + '(', n, num_open_p+1, num_closed_p)
          insert_p(res, ele + ')', n, num_open_p, num_closed_p+1)
        end
      end
    end
    

Log in to reply
 

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