Appending to a list vs concatenating in python recursive calls

Question

Please look at the following leetcode problem: https://leetcode.com/problems/generate-parentheses/

In it, you're trying to generate a series of parentheses with a couple of rules how each list of parenthesis should look like.

I am aware of two approaches, that seem functionally identical to me but only one works. I understand that append returns None and modifies in-place, but I fail to see how that affects the recursive process.

Here is the code that doesn't work:

class Solution:
    def generate(self, output, temp, n):
            if len(temp) == 2*n:
                output.append(temp)
            left_count = temp.count("(")
            right_count = temp.count(")")
            if left_count < right_count:
                return
            if left_count < n:
                self.generate(output, temp.append("("), n)
            if left_count > right_count:
                self.generate(output, temp.append(")"), n)


    def generateParenthesis(self, n: int) -> List[str]:      
        output = []
        self.generate(output, ["("], n)
        return output

This code (using concat) works:

class Solution:
    def generate(self, output, temp, n):
            if len(temp) == 2*n:
                output.append(temp)

            left_count = temp.count("(")
            right_count = temp.count(")")
            if left_count < right_count:
                return
            if left_count < n:
                self.generate(output, temp + "(", n)
            if left_count > right_count:
                self.generate(output, temp + ")", n)

    def generateParenthesis(self, n: int) -> List[str]:      
        output = []
        self.generate(output, "", n)
        return output

Could someone please clarify what I'm missing here? Thank you very much.

Answer 1

.append returns None instead of the appended list as one could expect. You want to add the parenthesis to temp first and then use the "updated" temp as an argument.

class Solution:
    def generate(self, output, temp, n):
            if len(temp) == 2*n:
                output.append(temp)

            left_count = temp.count("(")
            right_count = temp.count(")")
            if left_count < right_count:
                return
            if left_count < n:
                temp.append("(") # does not return anything but modifies temp.
                self.generate(output, temp, n)
            if left_count > right_count:
                temp.append(")") # same.
                self.generate(output, temp, n)


    def generateParenthesis(self, n: int) -> List[str]:      
        output = []
        self.generate(output, ["("], n)
        return output