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

Question

I've been trying to use backtracking to solve this problem but I am having problems with keeping track of the found answers.

My code:

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

When I tried to run this code it outputted this: [[], []]; But I expected this: [['255', '255', '11', '135'], ['255', '255', '111', '35']]; When I uncommented the two print()'s in the code it outputted this:

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

From this I deduct that my logic on the whole is correct but the answers stored in the ans variable of the Solution class got somehow messed up.

Can somebody help me with this problem?

Thanks and have a nice day!

Answer 1

python pass arguments by reference, so path that you append to ans and path.pop() are the objects

you need to copy the path object given to backtrack (path.copy()in py3, path[:]in py2):

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