Permutation using backtracking with Python-CodePudding

I am trying out the following backtracking solution for permutation of a list:

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)

It turns out after execution, you get:

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

Expected result is:

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

Could you help point out which part of the code goes wrong and why?

CodePudding user response：

Lists passed to a function in python are references by default. I changed backtrack(nums, used, track) to backtrack(nums, used, track.copy()) and it seemed to have solved the issue.

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)