How to use recursion to get subset by splitting the set to first one and rest part (python)

Question

I want to write a function using recursion to get the subset of a set and print like this when we input[1, 2, 3]as set:

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

My thinking is split the set to two part, the first one, and the rest. Then use the first one to append the every element in the rest list.

Here is my code:

def subset(set):
    if len(set) == 0:
        return [set]
    elif len(set) == 1:
        return [set[0]]
    else:
        short = subset(set[1:])
        alist=[]

        for item in short:  

            blist=[set[0]]
            blist.append(item)
            alist.append(blist)

        return alist

It doesn't work. How can I fix it?(only allow one parameter,set)

Answer 1

Assuming that the elements doesn't have any duplicates.

def subset(l):
    if not l:
        return [[]]
    rest = subset(l[1:])
    return rest + [[l[0]] + s for s in rest]

The output is not exactly in the same order as you require:

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

But we can try to sort the resulting list of subsets. Assuming the elements of the list are always integers we can try:

sorted(subset([1, 2, 3]), key=lambda l : int('0' + ''.join(str(i) for i in l)))

And then we have the desired output:

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