使用回溯创建给定列表的排列列表：我做错了什么？

Question

我正在尝试解决以下问题：

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

我已经实现了一个使用回溯完美打印所有排列的解决方案。但是，当我尝试将每个排列附加到列表并存储结果时，它不起作用。

这是我在 Python 中的代码：

存储列表所有排列的函数：

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]

return 排列列表的函数：

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

但是，出于某种原因，当我运行这样做时，它会用最近的 nums:

排列覆盖 ans_list 中的所有元素

预期输出：

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

实际输出：

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

我做错了什么？

Answer 1

ans_list.append(nums)

这只会将对同一个列表的引用一遍又一遍地添加到答案列表中。您想要的是在那个时间点捕获列表的快照。您可以通过复制列表来做到这一点。

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]

按预期工作：

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

注意：如果您的列表中有嵌套对象，您可能需要 deepcopy 列表。

使用回溯创建给定列表的排列列表：我做错了什么？

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

python

arrays

recursion

backtracking