why getting all possibilities of a list python don't work?

so I made a simple program which suppose to calculate all possible lists out of a given list.
for example [1,2,3]
the program suppose to return: [1,2,3], [2,3], [1,3], [1], [2], [3], []
but is ‘NoneType’ object has no attribute ‘append

def __bacteria(mass_list, count, option_list):
    if len(mass_list) == count:
        return option_list
    return __bacteria(mass_list,count+1, option_list.append(mass_list[count])) or __bacteria(mass_list,count+1, option_list)

>Solution :

So, why doesn’t it work? Let’s add some type annotations and run a type checker like MyPy, those help me personally figure out a lot of bugs:

def __bacteria(mass_list: list[int], count: int, option_list: list[int]) -> list[list[int]]:
    if len(mass_list) == count:
        return option_list  # error: list[int] given but list[list[int]] expected
    return __bacteria(mass_list, count + 1,
             option_list.append(mass_list[count]) # error: None given but list[int] expected
           ) or __bacteria(mass_list , count + 1, option_list)

Alright, so it shows 2 errors so far. What’s the first one? Well, you return the current option, rather than a list of the current option.

As for the second one, list.append modifies the list in place, and returns None. Neither of those are what you want. What you want is, as suggested by @Michael Butscher: option_list + [mass_list[count]]. So now we have:

def __bacteria(mass_list: list[int], count: int, option_list: list[int]) -> list[list[int]]:
    if len(mass_list) == count:
        return [option_list]
    return (__bacteria(mass_list, count + 1, option_list + [mass_list[count]]) or
            __bacteria(mass_list, count + 1, option_list))

That should not give any errors when running a type checker or when running the code. But I bet it prints out the wrong thing. How could that happen?

The base case (if len(mass_list) == count) should be fine. The first recursive call seems fine too, and the second recursive call is fine as well. What’s left? Only the or.

Now what does or do when given lists as arguments? Try it out on the interactive interpreter. What is the result of [] or []? And the result of [1] or [2]? And the result of [] or [0]? What is the logical rule that or implements when given two lists?

So what do we need here? Well, we know that __bacteria returns a list of lists (list[list[int]] to be precise) and we need to return a list of lists that contains the items of the list returned by the first recursive call and the items of the list returned by the second recursive call. That’s what + does! So now we have:

def __bacteria(mass_list: list[int], count: int, option_list: list[int]) -> list[list[int]]:
    if len(mass_list) == count:
        return [option_list]
    return (__bacteria(mass_list, count + 1, option_list + [mass_list[count]]) +
            __bacteria(mass_list, count + 1, option_list))

We can do better than this. For one, we’re building up a list by creating a lot of smaller lists and copying them to concatenate them multiple times. Try giving a larger mass_list, and see how your program slows down.

One way to make it faster and use less memory is by using a generator as a helper function. I’ll rename the function and arguments to make things clearer:

from typing import Iterator

def powerset(items: list[int]) -> list[list[int]]:
    return list(powerset_helper(items, 0, []))

def powerset_helper(items: list[int], index: int, to_include: list[int]) -> Iterator[list[int]]:
    if index == len(items):
        yield to_include
        return
    yield from powerset_helper(items, index + 1, to_include + [items[index]])
    yield from powerset_helper(items, index + 1, to_include)

We can do even better than this, though, which is to simply use the answer by @Dalmas Otieno! 🙂