Get subsets of a set given as a list This code is meant to create a list of subsets of a given set which is represented as a list.

I'm doing this to improve my style and to improve my knowledge of fundamental algorithms/data structures for an upcoming coding interview.

def subsets(s):
    if s == []:
        return [s]
    sets = [s]
    for i in range(0, len(s)):
        tmp_subsets = subsets(s[:i] + s[i+1:])
        for subset in tmp_subsets:
            if subset not in sets:
                sets.append(subset)
    return sets


I'm also not sure if using the set() data structure would be considered cheating in an interview context.

If there are any ideas about how to improve its performance without significantly compromising on readability I would also be open to that.
This is unnecessary:


if s == []:
    return [s]



You can safely remove it, the program will still work.

This step is not so great:


if subset not in sets:
    sets.append(subset)



For two reasons:


Checking if a list contains some items is an \$O(n)\$ operation
Comparing sets is not free either


A more efficient solution is to count from 0 until 1 &lt;&lt; n, and use the bitmap of the count to decide the elements that are part of a subset.

def subsets(s):
    sets = []
    for i in range(1 &lt;&lt; len(s)):
        subset = [s[bit] for bit in range(len(s)) if is_bit_set(i, bit)]
        sets.append(subset)
    return sets

def is_bit_set(num, bit):
    return num &amp; (1 &lt;&lt; bit) &gt; 0


That is, in a subset, each element may be either present, or not. So each element has only 2 possible states: in or out. 1 or 0. If we look at the binary representation of numbers from 0 to 2^n -1, where n is the number of elements, for example when n=3, we have:

    cba
0 = 000
1 = 001
2 = 010
3 = 011
4 = 100
5 = 101
6 = 110
7 = 111


There are 8 possible subsets, and the bits represent whether an element is in the subset or not.
This is the idea used by the program:


The outer loop goes from 0 until 2^n - 1.
The inner loop goes from 0 until n - 1.
1 &lt;&lt; bit is 1 shifted to the left bit times.


For example, when i = 3, that corresponds to bits 011.
We loop from 0 until 2, comparing i against 001, 010, and 100.
For these values, the expression i &amp; (1 &lt;&lt; bit) will be evaluated as
011 &amp; 001 = 001, 011 &amp; 010 = 010, and 011 &amp; 100 = 000, respectively.
The first two are greater than 0, the last one is not.