22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

class Solution {

    /**
     * @param Integer $n
     * @return String[]
     */
    function generateParenthesis($n) {
        $result = [];
        $this->helper(0, 0, $n, "", $result);
        return $result;
    }
    
    function helper($l, $r, $max, $str, &$result){
        if($l + $r == $max*2){
            $result[] = $str;
            return;
        }
        if($l < $max){
            $this->helper($l+1, $r, $max, $str."(", $result);
        }
        
        if($r < $l){
            $this->helper($l, $r+1, $max, $str.")", $result);
        }
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.