题目

分析

这道题要求生成指定数量的括号对，并且将它们全部输出。
结束条件就很明了了：
当左右括号都用完了就结束了。

并且字符串生成的顺序一般是从左到右，那么就必须要保证生成的字符串中，左括号的数量一定大于等于右括号，才能保证是有效的。

至于这道题为什么不用回溯，其实也就是没有显示的removelast而已。
下面代码给出来就明了了。

代码

还是用的Java实现，没办法，咱为了混口饭吃

  public List<String> generateParenthesis(int n) {
        List<String> res = new LinkedList<>();
        select(res, "", n, n);
        return res;
    }

    /**
     * @param res   返回结果
     * @param track track
     * @param left  剩余可用的左括号
     * @param right 剩余可用的右括号
     */
    public void select(List<String> res, String track, int left, int right) {
        //结束条件：左右括号都用完
        if (left == 0 && right == 0) {
            res.add(track);
        }

        //有效括号始终保证左括号数量是大于等于又括号的
        if (left > right) {
            return;
        }

        if (left > 0) {
            select(res, track + "(", left - 1, right);
        }
        if (right > 0) {
            select(res, track + ")", left, right - 1);
        }
    }

很清楚的看到：在select方法进行递归调用的时候，创建了一个新的String
track+"(" 来传入参数，这就相当于track.add(something);然后这次调用结束后，track还是原来那个track，就相当于removelast()了。
所以其实还是一个纯正的回溯。