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

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"))