Subset - 子集


问题


问题:

求拥有(n)个元素的集合(A = {a0,a_1,a_2, \cdots ,a{n-1} })的所有子集。


解法:

拥有(n)个元素的集合(A)的所有子集,可以看作从集合(A)中取出(0)个元素的所有组合、取出(1)个元素的所有组合、…取出(n-1)个元素的所有组合、取出(n)个元素的所有组合,这些所有组合即为所求。


具体从n个元素的集合中取出m个元素的所有组合,可以通过中的算法求出。因此子集问题只需要遍历所有元素个数即可。


该算法的时间复杂度为(O(2^n))。