Recursion in python - appending to a list

Question

I'm new to python and while practicing the language I've encountered a problem I could not understand.

My question is not about the algorithm itself, it is about references and recursion in 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]]

So I have a Class Solution:

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) will print all wanted subsets, but at the end im getting an empty list inside all_subsets

What am I missing? is all_subsets is passed by reference? what is happening under the hood?

In python things are a bit more complicated than just pass-by-reference — Er...
– Er..., Commented Jan 16, 2020 at 10:42

Sergio Ferrer Sánchez · Accepted Answer · 2020-01-16 10:38:03Z

3

By default, all lists are passed by reference. When you do all_subsets.append(current_sub) you are adding a reference to current_sub into all_subsets. Afterwards you empty current_sub by current_sub.pop(), so all the references you added point to an empty list.

To clarify, look at this example:

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

You can create a copy of a list with list[:]. So your line should look like:

 all_subsets.append(current_sub[:])

answered Jan 16, 2020 at 10:38

Sergio Ferrer Sánchez

3203 silver badges20 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Recursion in python - appending to a list

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest