Python3 .6, пытаясь добавить в список атрибутов во время рекурсивного возврата, но это отбрасывает результаты?

Question

Я пытаюсь сгенерировать все уникальные подмножества с помощью рекурсивного возврата. (подготовка к собеседованию). Постановка задачи: При заданном наборе различных целых чисел возвращаются все возможные подмножества (набор степеней). Примечание. Набор решений не должен содержать повторяющихся подмножеств.

Хотя для ввода [1,2,3] мой вывод для этого:

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

Когда ответ должен быть:

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

Хотя, когда я распечатываю то, что добавляю в свой список, он печатает правильные ответы:

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

I Я подумал, что это может быть проблемой с рекурсивной передачей этих списков, повторным их использованием и т. д. c, поэтому я сделал копии параметров. По какой-то причине мне нужно запустить копию моих параметров.

Мне не хватает понимания управления памятью этих структур данных? У меня возникла та же проблема при использовании этого подхода для других проблем с возвратом.

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

Я думаю, что ваша проблема в этой строке:

self.subset.append(frameCurrentSubset)

, где вы добавляете список в список, но позже вы

frameCurrentSubset.remove(option)

, где вы удаляете элемент из frameCurrentSubset. Но проблема в том, что вы также удаляете этот элемент из списка, который вы скопировали в self.subset, потому что это тот же список в памяти.

Решение заключается в использовании вместо этого:

self.subset.append(frameCurrentSubset[:])

, который добавит новый список, который содержит все элементы frameCurrentSubset на данный момент.

Полное решение:

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)