check this sample code for backtracking, there are two ways I can append the variable i to curr before backtracking, the one here (not commented) updates the global ans array, whereas the other way doesn't (shown below).:
n = 4
k = 2
ans = []
def backtrack(first, curr):
if len(curr)==k:
ans.append(curr)
for i in range(first, n+1):
# curr.append(i)
backtrack(i+1, curr+[i])
# curr.pop()
curr = []
backtrack(1, curr)
print("result = ",ans)
output here: result = [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
for the other way:
n = 4
k = 2
ans = []
def backtrack(first, curr):
if len(curr)==k:
ans.append(curr)
for i in range(first, n+1):
curr.append(i)
backtrack(i+1, curr)
curr.pop()
curr = []
backtrack(1, curr)
print("result = ",ans)
output here: result = [[], [], [], [], [], []]
I wish to understand, what exactly changes here and why the global output array ans behaves differently
curr+[i] creates a new object which gets passed to the next recursive call. So whenever you then append curr to ans with this version, you append a new object showing you a snapshot of what curr is which won't later get modified.
When you instead use .append and .pop, you keep passing and having only one single object, so when you append it to ans it is really that unique object that you append everytime again and again. Then you will keep updating that unique object which will reflect on all element of ans since they are the same object. Given at the end of processing curr gets cleared you end up having only empty lists everywhere, even if at every step curr had actually the value you wanted.
You can see that by adding this print first to check that apart from this bug, everything still works the same in both cases as you would expect:
def backtrack(first, curr):
print(first, id(curr), curr)
# ... and the rest
To fix the second version, you can pass a copy instead:
curr.append(i)
backtrack(i+1, curr.copy())
curr.pop()
or copy when you append to ans
ans.append(curr.copy())