如何用一个递归函数求一个集合的幂集

Question

如何用一个递归函数求一个集合的幂集

Answer 1

任取元素a属于A,把集合的所有子集分作两类,一类包含a,一类不包含.这样
如果f(A)表示A的所有子集的构成的集合,f可以这样实现（+表示集合求并）：
f(A) = f(A\{a}) + ({a}+f(A\{a}))
就是说,先把a拿掉,求A\{a}的幂集f(A\{a}),然后对f(A\{a})中的每个元素,
把a放进去,这样得到包含a的所有子集,加上f(A\{a}),就是所有A的子集.