调试 Leetcode 46 的回溯算法：排列问题？

Question

我正在使用回溯算法来解决经典问题。 Leetcode 排列问题.

给定一个由不同整数组成的数组

nums

，返回所有可能的排列。您可以按任意顺序返回答案。

这非常简单，我可以使用以下方法解决它 代码：

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:

        solutions = []
        def backtrack(state):
            # print(state)
            # print(remain)
            if len(state) == len(nums):
                solutions.append(state.copy())
                # return

            for n in nums:
                if n not in set(state):
                    state.append(n)
                    backtrack(state)
                    state.pop()

        state = []
        backtrack(state)
        return solutions

但是，当我尝试传递未选定元素（名为

remain

）的索引时，请参阅以下内容：

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:

        solutions = []
        def backtrack(state, remain):
            if len(state) == len(nums):
                solutions.append(state.copy())
                # return

            for i in remain:
                state.append(nums[i])
                remain.remove(i)
                backtrack(state, remain)
                state.pop()
                remain.add(i)

        full_ind = set([i for i in range(len(nums))])
        state = []
        backtrack(state, full_ind)
        return solutions

这不起作用，而且我的解决方案总是出现冗余。见下文： 我想我一定犯了一些愚蠢的错误，但我无法弄清楚。有人能帮我解决这个问题吗？我很难理解发生了什么。真的很感激:)!!

Answer 1

正如评论所说，您在迭代列表时正在修改列表。

当您将循环更改为：

时，您的第二个片段将起作用：

for i in list(remain):

将剩余传递给列表构造函数会根据原始集合创建一个列表，您可以在修改集合时对其进行迭代。