使用回溯查找排列

Question

我无法理解回溯解决方案。我对算法和递归很陌生。这是一个leetcode问题。 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

我正在努力解决这样一个事实：当我使用 nums = [2, 3] 调用该函数时，结果变量包含值 results = [[3, 2], [2, 3]]。随后，当返回这些排列并向其附加 1 时，我预计当遇到 results.extend() 时，结果应变为 results = [[3, 2], [2, 3], [3, 2, 1]、[2、3、1]]。你能帮我理解我可能错在哪里吗？”

我尝试干运行代码并在后续调用中打印变量的值，但无法破译这个概念

Answer 1

看起来您认为

results

是一个 single 变量，但事实并非如此：函数

permutute

的每次执行都有其自己的本地

result

列表。

results.extends

仅影响这些局部变量之一，而不影响函数的 caller 本地的同名变量。

当结果

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

返回给调用者时，调用者的

result

列表仍然为空——它与用于获取

result

的

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

变量没有任何联系。 那个后一个

result

变量不再存在，因为一旦你从返回

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

的递归调用中返回，它就不再存在了。