Creating a list of permutations of a given list using backtracking: what am I doing wrong?

Question

I'm trying to solve the following question:

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

I've implemented a solution using backtracking that prints all the permutations perfectly. However, when I try to append each permutation to a list and store the result, it doesn't work.

Here is my code in Python:

Function to store all permutations of list:

def myRec(nums, l, r, ans_list):
    if(l == r):
        #print(nums) (this works perfectly!)
        ans_list.append(nums) #this does not
        return 
    for i in range(l, r+1):
        nums[i], nums[l] = nums[l], nums[i]
        myRec(nums, l+1, r, ans_list)
        nums[i], nums[l] = nums[l], nums[i]

Function to return the list of permutations:

def permute(nums: List[int]) -> List[List[int]]:
    ans_list = []
    myRec(nums, 0, len(nums)-1, ans_list)
    return ans_list

However, for some reason when I run this it overwrites all the elements in ans_list with the most recent permutation of nums:

Expected output:

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]

Actual output:

[[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]]

What am I doing wrong?

Answer 1

ans_list.append(nums)

This will just add the reference to the same list over and over again to the answer list. What you want is to capture a snapshot of the list at that point in time. You can do that by making a copy of the list.

def myRec(nums, l, r, ans_list):
    if l == r:
        ans_list.append(nums.copy())  # add a copy of the list
        return
    for i in range(l, r + 1):
        nums[i], nums[l] = nums[l], nums[i]
        myRec(nums, l + 1, r, ans_list)
        nums[i], nums[l] = nums[l], nums[i]

Which works as expected:

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]

Note: if you have nested objects in your list, you might need to deepcopy the list instead.