生成括号的问题

Question

我一直在尝试在 Leetcode 上编写生成括号问题，但我一直得到 "Memory Limit Exceeds"，这意味着我的代码中有一个无限循环。但是，我无法理解为什么会有无限loop/recursion。谢谢！

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> permutations = new ArrayList<String>();
        permute(permutations, "" , n, n);
        return permutations;
    }

    public void permute (List<String> permutations, String paren, int left, int right){

        if(left == 0 && right == 0){
            permutations.add(paren);
            return;
        }
        if(left > 0){
            permute(permutations, paren + "(", left--, right);
        }
        if(right > left){
            permute(permutations, paren + ")", left, right--);
        }

    }
}

Answer 1

您正在使用参数 left-- 进行调用，它将再次使用参数 left 的相同值调用该方法；只有在你的函数 returns 之后，参数 left 减一

但这也不能解决你的问题，你必须提供 left-1 比如：

permute(permutations, paren + "(", left-1, right);

右边也类似：

permute(permutations, paren + ")", left, right-1);

left-- 当函数 returns 不是你想要的时减少值。

生成括号的问题

Problem with Generate Parenthesis Problem

algorithm

recursion

backtracking

parentheses