Generate all subsets of a string using recursion

Question

string = 'abc'. All subsets of said string are: [a b c ab abc ac bc '(empty string)'].
I need to generate all of these subsets using a recursive function, but I can't figure out how.

Answer 1

For each char recur to use and not use

s = 'abc'

def recur(s, prefix, out):
    if len(s) > 0:
        recur(s[1:], prefix+s[0], out)
        recur(s[1:], prefix, out)
        out.append(prefix+s[0])
    return out

print recur(s, '', [''])

outputs

['', 'abc', 'ac', 'ab', 'bc', 'c', 'b', 'a']

Answer 2

Just for kicks, you can write it as a one line lambda.

lambda s: { s[j:(j+i)] for i in range(len(s)+1) for j in range(len(s)-i+1) }