Power set solution in **O(n) time** and **O(n) space** complexities?

Question

Is it possible to find all possible subsets of set in (i.e. power set) in O(n) time and O(n) space complexities?

Program in put >> {a,b,c}

Expected out put in O(n) time and O(n) space complexity, here n is 3.

{}, {a}, {b}, {c}, {a,b}, {b,c}, {a,c}, {a,b,c}

Answer 1

Time-complexity

No. Time complexity will always be bounded below by the size of the output. Since the powerset of a set of size n has size 2ⁿ, there exist no algorithm to find the powerset in less than O(2ⁿ).

Space-complexity

In term of total space, since the size of the output is 2ⁿ, you cannot do any better than O(2ⁿ).

Although in term of auxiliary space, given a set s of size n, any element of the powerset can be represented by a binary string of length n. Each position representing whether an element x of s is in the set.

By example, given the set {a, b, c}, the string 101 represents the subset {a, c}.

In particular since a binary string is a representation of an integer, you can define some order on your set and enumerate its elements. This requires, as intermediate storage, nothing but a single integer which, in size, takes no more than O(n).

This is especially useful in languages implementing generators where you can traverse all the elements if the powerset with nearly no auxiliary storage.