I am having trouble understanding a backtracking solution. I am new to algorithms and recursion. This is a leetcode problem. Leetcode 46.
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
results = []
if len(nums) == 1:
return [nums[:]]
for _ in range(len(nums)):
n = nums.pop(0)
perms = self.permute(nums)
for perm in perms:
perm.append(n)
results.extend(perms)
nums.append(n)
return results
I am struggling with the fact that when I invoke the function with nums = [2, 3], the results variable contains the values results = [[3, 2], [2, 3]]. Subsequently, when these permutations are returned and 1 is appended to them, I expected that when results.extend() is encountered, the results should become results = [[3, 2], [2, 3], [3, 2, 1], [2, 3, 1]]. Can you help me understand where I might be mistaken?”
I tried dry running the code and printing the value of variables at subsequent calls, but could not decipher the concept
It looks like you think of results as a single variable, but that is not true: every execution of the function permutute has its own, local result list. results.extends only affects one of those local variables, not the variable with the same name that is local to the caller of the function.
When the results [[3, 2], [2, 3]] are returned to the caller, the caller’s result list is still empty — it has no connection with the result variable that was used to get [[3, 2], [2, 3]]. That latter result variable no longer exists, as it stopped being something as soon as you got back from the recursive call that returned [[3, 2], [2, 3]].