使用递归生成字符串的所有子集

Question

给定一个字符串 string = 'abc'，这个字符串的所有子集是：[a b c ab abc ac bc '(空字符串)']。
我需要用一个递归函数来生成所有这些子集，但我不知道该怎么做。

Answer 1

为了好玩，你可以把它写成一行的lambda表达式。

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

Answer 2

对于每一个字符，递归地决定是使用它还是不使用它。

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, '', [''])

输出结果

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