回溯法跟踪答案异常排查：IP地址恢复Python代码求助

你遇到的问题根源在于Python中列表是可变对象，传递的是引用而非值。你的回溯逻辑本身是正确的，但在将path添加到self.ans时，直接添加了对原列表的引用，后续的path.pop()操作会修改这个引用指向的列表，最终导致self.ans里的所有元素都变成了空列表。

具体原因 #

当你执行self.ans.append(path)时，并没有把path当前的内容复制一份存到ans里，而是把path这个列表的"地址"存了进去。后续回溯过程中，path.pop()会不断移除元素，最后path被清空，而ans里的所有元素都是指向同一个path对象的引用，所以最终输出就是[[], []]。

修复方法 #

只需要在添加到ans时，创建一个path的副本即可。可以用以下几种方式实现：

• self.ans.append(path.copy())
• self.ans.append(list(path))
• self.ans.append(path[:])

修改后的完整代码 #

class Solution:
    def restore_ip(self, s):
        self.ans = []
        self.backtrack([], s)
        return self.ans
    def backtrack(self, path, s):
        if s == "" and len(path) == 4:
            # 添加path的副本，而不是引用
            self.ans.append(path.copy())
            return
        if s == "" or len(path) >= 4:
            return
        for i in range(1, len(s)+1):
            if i > 3:
                break
            if int(s[:i]) > 255:
                break
            if i != 1 and s[0] == 0:
                break
            path.append(s[:i])
            self.backtrack(path, s[i:])
            path.pop()
a = Solution()
print(a.restore_ip("25525511135"))

运行结果 #

执行修改后的代码，会输出你期望的结果：

[['255', '255', '11', '135'], ['255', '255', '111', '35']]

内容的提问来源于stack exchange，提问作者Danny Ye