This is the code I came up with:

```
def combinations(input):
    ret = ['']
    for i in range(len(input)):
        ret.extend([prefix+input[i] for prefix in ret])
    return ret

```

This algorithm is O(2^n) time, but can space be reduced? I heard using `yield` might work, but having trouble thinking through how to implement with `yield`. Please don't use the built in combination function -- I would like to see how it's implemented.