Рекурсия в python - добавление в список - PullRequest
Новая
       5

Рекурсия в python - добавление в список

1 голос
/ 16 января 2020

Я новичок в python и, практикуя язык, столкнулся с проблемой, которую не мог понять.

Мой вопрос не о самом алгоритме, а о ссылках и рекурсии в python

# Background

Given a set of distinct integers, nums, return all possible subsets (the power set).
Example:

Input: nums = [1,2,3]
Output:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Итак, у меня есть решение класса: 

class Solution:
    def find_subsets(self , nums , current_sub , all_subsets , index):
        # print(current_sub) This will print the wanted results list

        all_subsets.append(current_sub) # Here the all_subsets list will be [1][1] , [1,2] [1,2] [1,2]

        if index < len(nums):
            for i in range(index , len(nums)):
                current_sub.append(nums[i])
                self.find_subsets(nums , current_sub , all_subsets ,i + 1)
                current_sub.pop()

    # Entery point         
    def subsets(self, nums: List[int]) -> List[List[int]]:
        current_sub = []
        all_subsets = []
        self.find_subsets(nums , current_sub , all_subsets , 0)
        return all_subsets # output -> [[],[],[],[],[],[],[],[]]

print(current_sub) напечатает все нужные подмножества, но в конце я получу пустой список внутри all_subsets

Чего мне не хватает? all_subsets передается по ссылке? что происходит под капотом?

1 Ответ

3 голосов
/ 16 января 2020

По умолчанию все списки передаются по ссылке. Когда вы делаете all_subsets.append(current_sub), вы добавляете reference к current_sub в all_subsets. После этого вы очищаете current_sub на current_sub.pop(), поэтому все добавленные вами ссылки указывают на пустой список.

Чтобы уточнить, посмотрите на этот пример: 

>>> a = []
>>> b = [1,2,3]
>>> a.append(b)
>>> a
[[1, 2, 3]]
>>> b.pop()
3
>>> a
[[1, 2]]
>>> b.pop()
2
>>> a
[[1]]
>>> b.pop()
1
>>> a
[[]] # <-- Here you have your empty list
>>>

Вы можете создать копию списка с помощью list[:]. Поэтому ваша строка должна выглядеть так: 

 all_subsets.append(current_sub[:])
...