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

Question

我一直在尝试使用回溯来解决 this problem 但我在跟踪找到的答案时遇到问题。

我的代码：

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']]
[[], []]

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

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

谢谢，祝你有愉快的一天！

Answer 1

python 通过引用传递参数，因此您附加到 ans 和 path.pop() 的 path 是对象

你需要复制给回溯的路径对象（path.copy()在py3中，path[:]在py2中）：

self.backtrack(path.copy(), s[i:])
               ^^^^^^^^^^^

Answer 2

您应该通过 return 值跟踪解决方案的状态。

找到解决方案后，您 return True 并停止回溯。

P.S.

您可以将方法转换为静态方法，因为答案独立于 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"))

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

How can I reliably keep track of answers when using backtracking?

python

recursion

backtracking