python - 递归只生成一对。我究竟做错了什么？

Question

我正在尝试根据输入列表创建排列。我的递归失败了，只带回了一个应该有多个列表的列表。 我不确定我的逻辑有什么问题 - 递归的新手。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        answer, perm = [], []
        self.dfs(nums, answer, perm)
        return answer

    def dfs(self, nums, answer, perm):
        if not nums:
            answer.append(perm)

        for ind, ele in enumerate(nums):
            perm.append(ele)
            nums.pop(ind)
            self.dfs(nums,answer, perm)

预期:[[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2 ,1]] 实际:[[1,2,3]]

Answer 1

注销一些通过您的解决方案的数据会很有帮助，这样您就可以准确地看到自己做错了什么。如果我们在您的代码的每一步记录 nums 和 perm，我们会得到以下信息:

[1, 2, 3]             # nums 0
[]                    # perm 0
[2, 3]                # nums 1
[1]                   # perm 1
[3]                   # nums 2
[1, 2]                # perm 2
[]                    # nums 3
[[1, 2, 3]]           # result

您当前所有的代码都将元素从列表移动到包含原始列表的子列表。您需要跟踪哪些元素已添加到子列表而不清空原始列表，然后您可以创建所需的排列。您仍然可以通过递归来完成此操作，但添加 set 的功能将使您的生活变得更加轻松。

这是一个基本示例，您可以根据需要进行调整:

def dfs(data, perm_out=None):
    if not perm_out:
        perm_out = []
    if not data:
        return [perm_out]
    res = []
    for point in data:
        u = {point}
        diff = data - u
        res += dfs(diff, perm_out + [point])
    return res

在您的简单输入数据上调用它:

i = [1, 2, 3]
u = dfs(set(i))
print(u)

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