使用 Python 回溯排列

Question

我正在尝试以下用于列表排列的回溯解决方案：

nums=[1, 2, 3]

def permute(nums):

    res = []
    track = []
    used = [0 for _ in range(len(nums))]

    def backtrack(nums, used, track):
        if len(track) == len(nums):
            res.append(track)
            return
        
        for i in range(len(nums)):
            if used[i]:
                continue
            track.append(nums[i])
            used[i] = 1
            backtrack(nums, used, track)
            track.pop()
            used[i] = 0
    
    backtrack(nums, used, track)

    return res

res = permute(nums)
print(res)

执行后得到：

[[], [], [], [], [], []]

预期结果是：

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

您能帮忙指出代码的哪一部分出错以及为什么吗？

Answer 1

在 python 中传递给函数的列表默认是引用。我将 backtrack(nums, used, track) 更改为 backtrack(nums, used, track.copy()) 似乎已经解决了问题。

nums=[1, 2, 3]

def permute(nums):

    res = []
    track = []
    used = [0 for _ in range(len(nums))]

    def backtrack(nums, used, track):
        if len(track) == len(nums):
            res.append(track)
            return
        
        for i in range(len(nums)):
            if used[i]:
                continue
            track.append(nums[i])
            used[i] = 1
            backtrack(nums, used, track.copy())
            track.pop()
            used[i] = 0
    
    backtrack(nums, used, track)

    return res

res = permute(nums)
print(res)

使用 Python 回溯排列

Permutation using backtracking with Python

python

list

append

permutation

backtracking