Generate Parentheses

给定一个正整数n，求出所有可能的n对括号的组合

递归的定律<条件，临时结果，终极结果>。本题最难想的点是条件是什么，思考过程中考虑过中间态，比如n=1的时候是一种状况，n=2的时候是在n=1的基础上进行叠加，但是这个叠加的过程太麻烦，太麻烦

思路1

以左括号和右括号剩余的个数作为条件， $left和$right两个变量代表目前还剩余的左括号和右括号，那么这个递归的终止条件就是右括号用完了，即$right=0的时候，此时的中间状态out的存储值就是结果集中间的一个，所以需要加上$res[] = $out，还有另外两种肯定需要return的条件，一个是$left <= 0, 另一个是$left > $right,因为这两种条件下，剩余的括号一定不能组成一种成对的模式。考虑好了终止条件，接下来考虑递归的条件，分为三个方向，

• left == right
  此时下一个需要放置的一定是左括号，所以是left -1,out = out . '(' ，然后继续迭代
• left < right
  此时下一个可能放左括号，也可能放右括号，left -1,out = out . '(' ，然后继续迭代。且right -1,out = out . ')' ，然后继续迭代

  /**
     * @param Integer $n
     * @return String[]
     */
    function generateParenthesis($n) {
        $left  = $n;
        $right = $n;
        $out   = "";
        $res   = [];
        $this->generateDFS($left, $right, $out, $res);
        return $res;
    }

    function generateDFS($left, $right, &$out, &$res) {

        if ($right <= 0) {
            $res[] = $out;
            return;
        }

        if ($left <= 0) {
            $out = $out . ")";
            $this->generateDFS($left, $right - 1, $out, $res);
            return;
        }

        if ($left > $right) {
            return;
        }

        if ($left < $right) {
            $leftOut = $out . "(";
            $this->generateDFS($left - 1, $right, $leftOut, $res);

            $rightOut = $out . ")";
            $this->generateDFS($left, $right - 1, $rightOut, $res);
        }

        if ($left == $right) {
            $leftOut = $out . "(";
            $this->generateDFS($left - 1, $right, $leftOut, $res);
        }
    }

思路2

参考：https://www.cnblogs.com/grandyang/p/4444160.html

同样是递归，递归条件貌似可以精简

    function generateParenthesis2($n) {
        $left  = $n;
        $right = $n;
        $out   = "";
        $res   = [];
        $this->generateDFS2($left, $right, $out, $res);
        return $res;
    }

    function generateDFS2($left, $right, &$out, &$res) {
        if ($left < $right) {
            return;
        }

        if ($left == 0 && $right == 0) {
            $res[] = $out;
            return;
        }

        if ($left > 0) {
            $leftOut = $out . "(";
            $this->generateDFS($left - 1, $right, $leftOut, $res);
        }

        if ($right > 0) {
            $rightOut = $out . ")";
            $this->generateDFS($left, $right - 1, $rightOut, $res);
        }
    }