Returning all the subsets. (Issue with recursion)

Question

class Solution(object):
    lista=[]
    def subsets(self, nums):
        subset=[]
        i=0
        self.helper(nums,subset,i)
        return self.lista
    def helper(self,nums,subset,i):
        if(i==len(nums)):
            print(self.lista)
            self.lista.append(subset)
            print(subset)
            
            return 

        subset.append(nums[i])
        self.helper(nums,subset,i+1)
        subset.pop()
        self.helper(nums,subset,i+1)
            
            

        
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

So the question is https://leetcode.com/problems/subsets/ Can someone help me understand where I am going wrong? My code only returns an empty list. I understand that the last call of the recursion returns nullset but my lista is declared globally and so whenever I append something in the base case of the recursion function, shouldn't it append to the existing global list?. So, should it not append that to the lista and work properly? Any help is appreciated.

If you'd like an alternative to recursion, you could iterate from 0 through 2^(len(nums)) - 1, and use the set bits as indices of nums to include. E.g. if the list has size three, you'd iterate through: 000, 001, 010, 011, 100, 101, 110, 111. — Dave, Jan 21 '21 at 17:05

Daniel Hao · Answer 1 · 2021-01-21T17:09:13.620

for this recursion it can be simplified as the following: (you can compare and see the difference then)

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return [[]]
        without = self.subsets(nums[1:])

        return without + [s + [nums[0]] for s in without]

Or a simple straight-forward iterative can do the work too:

 def subsets(self, nums):
     result = [[]]  
        
     for n in nums:
         result += [x+[n] for x in result]
            
     return result

score 0 · Accepted Answer · answered Jan 21 '21 at 17:10

Your logic for generating subsets is fine. The main issue here is that self.lista.append(subset) inserts a reference to subset into lista. You can read more about object references in relation to lists here.

This means that any changes you make to subset will persist in all references of subset in lista. In this case, the final state of subset will be an empty list, hence lista contains a bunch of empty lists [].

One way to fix this would be to make a copy of subset on insertion, i.e change

self.lista.append(subset)

to

self.lista.append(subset.copy()) (if you're using Python >= 3.3, otherwise you can slice it or use copy).

Returning all the subsets. (Issue with recursion)

2 Answers2