问一道算法题

erduo100

Write a recursive function to output all subsets of elements.  for  example, the subsets of the three-element set {a, b, c} are {}(empty set), [a}, {b}, {c},{a, b}, {a,c}, {b,c}, {a,b,c}

我知道怎么用非递归解决这个问题，但递归想了下没想出来。

win_hate

我的 blog  上有一个贴子讨论了如何生成不同的组合，一个子集其实就是一个组合，所以可以用生成不同组合的方法来得到全体子集。设你的集合有 n 个元素，只要取其大小为0 的子集合(组合)，大小为 1 的(组合)，...., 大小为 n 的子集(组合) 就行了.

另一种方法称为比特集，其想法为把 n 个元素对应到 n 个 bit 上去，bit 为1 表示元素出现，bit 为 0表示元素不出现。这些 bits 的 2^n 个状态恰好与 2^n 个子集对应。比如全0表示空集，全1表示全集合。而 2^n 个比特可以对应成一个整数，所以把一个整数从0增长到 2^n-1，起 bit 模式就刻画了所有子集。


我前面给出的第一种方法可看作是某种形式的递归。

[ 本帖最后由 win_hate 于 2006-3-3 21:13 编辑 ]

erduo100

这是一本算法书上第一章的题， 应该用不到这些离散数学的知识，我估计用几个循环和递归就可以解决了

win_hate

若要单纯的递归，应该很简单：

A={a, b....} 的子集有两类，一类含  a，一类 不含 a，后者是 A\{a}={b...} 的子集。只要递归到 A\{a} 上，就得到了第二类。然后把 a 第插入第二类，得到第一类就行了。


ps> 我前面提到的算法也就是几个循环而已。

erduo100

对 就是这样的！
谢谢了 斑竹