Python3.6, trying to append to a attribute list during recursive backtracking, but it discards results?

Question

I am trying to generate all unique subsets using recursive backtracking. ( interview prep ). The problem statement is: Given a set of distinct integers, nums, return all possible subsets (the power set). Note: The solution set must not contain duplicate subsets.

Though, for the input [1,2,3] my output for this is:

[[],[],[1],[1,2],[1],[],[2],[]]

When the answer should be:

[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Though, when I print out what I am appending to my list it prints the correct answers:

[1]
[1, 2]
[1, 2, 3]
[1, 3]
[2]
[2, 3]
[3]

I thought that it could be an issue with passing these lists recursively, reusing them etc so I made copies of the params. For some reason I have to run a copy on my parameters as well.

Am i missing an understanding of the memory management of these data structures? I have been having the same issue when taking this approach for other backtracking problems.

class Solution:
    def __init__(self):
        self.subset = [[]]

    def subsets(self, nums: List[int]) -> List[List[int]]:
        self.initSubsets(nums,[])
        return self.subset

    def initSubsets(self,options,currentSubset):
        frameOptions = options.copy()
        frameCurrentSubset = currentSubset.copy()

        for option in options:
            # add option to subset
            frameCurrentSubset.append(option)
            # add to solution
            self.subset.append(frameCurrentSubset)
            print(frameCurrentSubset)
            # guarentee no dups
            frameOptions.remove(option)
            # recurse
            self.initSubsets(frameOptions,frameCurrentSubset)
            # undo changes
            frameCurrentSubset.remove(option)

        return

Answer 1

I think that your problem is at this line:

self.subset.append(frameCurrentSubset)

where you append a list to a list but later you

frameCurrentSubset.remove(option)

where you remove an element from frameCurrentSubset. But the problem is by doing that you also remove that element from the list you have copied to self.subset because it's the same list in memory.

The solution is to use instead:

self.subset.append(frameCurrentSubset[:])

which will append a new list that contains all the elements of frameCurrentSubset at that moment.

A complete solution is:

from typing import List

class Solution:
    def __init__(self):
        self.subset = [[]]

    def subsets(self, nums: List[int]) -> List[List[int]]:
        self.initSubsets(nums,[])
        return self.subset

    def initSubsets(self,options,currentSubset):
        frameOptions = options.copy()
        frameCurrentSubset = currentSubset.copy()

        for option in options:
            # add option to subset
            frameCurrentSubset.append(option)
            # add to solution
            self.subset.append(frameCurrentSubset[:])
            print(frameCurrentSubset)
            # guarentee no dups
            frameOptions.remove(option)
            # recurse
            self.initSubsets(frameOptions,frameCurrentSubset)
            # undo changes
            frameCurrentSubset.remove(option)

        return

example = Solution()
result = example.subsets([1, 2, 3])
print(result)