LeetCode22括号生成递归传参open+1与++open的差异问题

核心差异 #

两种写法的本质区别是是否会修改当前作用域的变量值，这刚好是回溯算法的核心敏感点：

• open+1是值计算表达式，仅基于当前open的值生成加1后的临时值传递给下层递归，当前层的open变量本身不会发生任何变化，递归回溯后后续逻辑仍然使用原值计算，完全符合回溯的状态一致性要求。
• ++open是前置自增操作，执行时会先把当前作用域内的open变量本身的值加1，再把修改后的值传递给下层递归。等递归回溯回到当前层时，open已经是加过1的错误值，后续执行if (close < open)的判断逻辑完全失准，最终生成不符合要求的括号组合。

注意：就算换成后置自增open++也会出现相同问题，因为不管前置还是后置自增，都会修改当前层的原变量，只是传参的值不同而已，都不符合回溯的状态要求。

回溯场景传参注意点 #

回溯算法的核心原则是递归前后的上下文状态完全一致，除了代码中显式编写的撤销操作（比如示例中的cur.deleteCharAt）之外，不要隐式修改当前层的状态变量。因此传递递增值时，直接使用变量+1的形式是最稳妥的写法，不会意外污染当前层的状态。 #

原正确参考代码 #

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList();
        backtrack(ans, new StringBuilder(), 0, 0, n);
        return ans;
    }

    public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max){
        if (cur.length() == max * 2) {
            ans.add(cur.toString());
            return;
        }

        if (open < max) {
            cur.append("(");
            backtrack(ans, cur, open+1, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }
        if (close < open) {
            cur.append(")");
            backtrack(ans, cur, open, close+1, max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

内容的提问来源于stack exchange，提问作者epoch21