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



• The inner loop goes from 0 until n - 1.






• 1

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 & (1 << bit) will be evaluated as
011 & 001 = 001, 011 & 010 = 010, and 011 & 100 = 000, respectively.
The first two are greater than 0, the last one is not.

StackExchange Code Review Q#147633, answer score: 8