# 8.4. Power set

> Write a method that returns all subsets of a set

```python
def power_set(lst, subsets=[]):
    for el in lst:
        if len(el) > 0:
            subsets.extend(power_set(el, subsets))
    subsets.append(lst)
    return subsets

lst = [1, 2, [3, 4], [[5], [6,7]]]
subsets = power_set(lst)
```

## Hints

I understood the problem wrong. 

* If you have {a, b}, all the subsets are: a, b, ab
* If you have {a, b, c}, all the subsets are: [a, b, ab], c, ac, bc, abc
* If you have {a, b, c, d}, all the subsets are: [a, b, ab, c, ac, bc, abc], ad, bd, cd, abd, acd, bcd, abcd.

For any new letter, add the last letter to all the subsets and append.

> You can also map each subset to a binary number, the `i`th bit could represent a 'boolean' flag for whether an element is in the set.

I can also use a python set.

```python
def power_set(lst):
    subsets = set()
    subsets.add(lst[0])
    for el in lst:
        for subs in subsets:
            subsets.add(subs + el)
        subsets.add(el)
    return subsets

power_set([1, 2, 3, 4])
```

The complexity of this algorithm is O(n * 2^n) in space and time.