使用回溯时如何可靠地跟踪答案？

Question

我一直在尝试使用回溯来解决这个问题，但在跟踪找到的答案方面遇到了问题。

我的代码：

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:

            #print(self.ans)

            self.ans.append(path)

            #print(self.ans)

            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']]：当我取消注释代码中的两个 print() 时，它输出以下内容：

[['255', '255', '11', '135']]

[['255', '255', '111', '35'], ['255', '255', '111', '35']]

[[], []]

由此我推断我的逻辑总体上是正确的，但存储在类ans变量中的答案Solution不知何故搞砸了。

有人可以帮我解决这个问题吗？

感谢，并有一个愉快的一天！

Answer 1

python 通过引用传递参数，以便path您附加到ans和path.pop()是对象您需要复制给回溯的路径对象（path.copy()在 py3 中，path[:]在 py2 中）：self.backtrack(path.copy(), s[i:])                ^^^^^^^^^^^

Answer 2

您应该通过返回值来跟踪解决方案的状态。当找到解决方案时，您返回True并停止回溯。聚苯乙烯您可以将该方法转换为静态方法，因为答案与对象状态无关Solution，从而能够使用不同线程解决多个问题。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:            self.ans = path            return True        if s == "" or len(path) >= 4:            return False        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])            if self.backtrack(path, s[i:]):                return True            path.pop()a = Solution()# ['255', '255', '11', '135']print(a.restore_ip("25525511135"))