CODEWITHSUNDEEP
algorithmrecursionbacktrackingparentheses
Jennifer Zhou
Jennifer Zhou

Reputation: 343

Problem with Generate Parenthesis Problem

I have been trying to program the Generate Parenthesis problem on Leetcode, but I keep on getting "Memory Limit Exceeds", which means that I have an infinite loop in my code. However, I cannot understand why there will be infinite loop/recursion. Thank you!

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--);
        }

    }
}

Upvotes: 0

Views: 94

Answers (1)

SomeDude
SomeDude

Reputation: 14238

You are calling with parameter left-- it will call the method again with the same value for the parameter left; only after your function returns, the parameter left is reduced by one.

But this is also not going to solve your problem, you have to supply left-1 like :

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

and similarly for right:

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

left-- reduces the value when the function returns which is not what you want.

Upvotes: 1

Related Questions