Python class variable getting changed after method ends for not applying deepcopy to list

Question

Was trying to solve this leetcode question in python using backtracking -

Given a string s, partition s such that every substring of the partition is a palindrome. 
Return all possible palindrome partitioning of s.

Getting weird output for this solution -

class Solution:
    
    a = list()

    def backtrack(self, start, string, palindrome, stack):

        if start == len(string):
            self.a.append(stack)
            return
        if start == len(string)-1:
            stack.append(string[start])
            self.a.append(stack)
            stack.pop()
            return

        for end in range(start, len(string)):
            if start == end:
                stack.append(string[start])
                self.backtrack(start+1, string, palindrome, stack)
                stack.pop()

            elif string[start] == string[end] and ((end == start+1) or palindrome[start+1][end-1]):
                stack.append(string[start:end+1])
                palindrome[start][end] = True
                self.backtrack(end+1, string, palindrome, stack)
                stack.pop()

    def partition(self, string):
        stack =  []
        self.a.clear()
        palindrome = [[False for __ in range(len(string))] for _ in range(len(string))]
        for i in range(len(string)):
            palindrome[i][i] = True
        self.backtrack(0, string, palindrome, stack)
        return self.a

Input: aab

Output :

[[],[]]

This code works, just changed list to set and made other minor changes

class Solution:
    
    a = set()

    def backtrack(self, start, string, palindrome, stack):

        if start == len(string):
            if ",".join(stack) not in self.a:
                self.a.add(",".join(stack))
            return
        if start == len(string)-1:
            stack.append(string[start])
            if ",".join(stack) not in self.a:
                self.a.add(",".join(stack))
            stack.pop()
            return

        for end in range(start, len(string)):
            if start == end:
                stack.append(string[start])
                self.backtrack(start+1, string, palindrome, stack)
                stack.pop()

            elif string[start] == string[end] and ((end == start+1) or palindrome[start+1][end-1]):
                stack.append(string[start:end+1])
                palindrome[start][end] = True
                self.backtrack(end+1, string, palindrome, stack)
                stack.pop()

    def partition(self, string):
        stack = answer = []
        palindrome = [[False for __ in range(len(string))] for _ in range(len(string))]
        for i in range(len(string)):
            palindrome[i][i] = True
        self.backtrack(0, string, palindrome, stack)
        ans = [item.split(",") for item in self.a]
        self.a.clear()
        return ans

Input: aab

Output: [["a","a","b"],["aa","b"]]

Question : https://leetcode.com/problems/palindrome-partitioning/

Answer 1

Figured it out! I have to apply copy.deepcopy while appending stack in the first code.

from copy import deepcopy

a = list()

def backtrack(self, start, string, palindrome, stack):

    if start == len(string):
        dc = deepcopy(stack)
        self.a.append(dc)
        return
    if start == len(string)-1:
        stack.append(string[start])
        dc = deepcopy(stack)
        self.a.append(dc)
        stack.pop()
        return

In python copy of a list doesn't make a new object always. For example -

>>> l=[1,2,3,4]
>>> x = l
>>> del l[1]
>>> l
[1, 3, 4]
>>> x
[1, 3, 4]

In the above code, x and l point to the same list

On using copy.deepcopy , a new list is created -

>>> from copy import deepcopy
>>> l=[1,2,3,4]
>>> x = deepcopy(l)
>>> del l[1]
>>> l
[1, 3, 4]
>>> x
[1, 2, 3, 4]