Playing on leetcode coding problem: “Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.”
I realized that my understanding of Python was not so good. I always thought that: since list are mutable object they are kind of passed by reference; so i always try to make a copy of the list before feeding the function to avoid inappropriate behavour as i did below:
class Solution: def generateParenthesis(self, n: int) -> List(str): res = () def add_parenthesis(l,o,f): if len(l)==2*n: res.append("".join(l)) return if f<o: return if o>0: lp = l.copy() lp.append("(") add_parenthesis(lp,o-1,f) if f>0: lm = l.copy() lm.append(")") add_parenthesis(lm,o,f-1) add_parenthesis(('('),n-1,n) return res
My friend wrote the folowing solution without bothering in feeding the recursive function with a copy of the list (S). I would expect that the final solution contain only the last change in S (it would be the case if we play alwas on the same reference), but it seems to work without any problem! What is wrong in my thinking ?
class Solution: def generateParenthesis(self, n: int) -> List(str): ans = () def backtrack(S = (), left = 0, right = 0): if len(S) == 2 * n: ans.append("".join(S)) return if left < n: S.append("(") backtrack(S, left+1, right) S.pop() if right < left: S.append(")") backtrack(S, left, right+1) S.pop() backtrack() return ans