CODEWITHSUNDEEP
algorithmbig-osubsetsubset-sum
RiyasAbdulla
RiyasAbdulla

Reputation: 171

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

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}

Upvotes: 4

Views: 750

Answers (1)

Olivier Melançon
Olivier Melançon

Reputation: 22294

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 2n, there exist no algorithm to find the powerset in less than O(2n).

Space-complexity

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

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.

Upvotes: 6

Related Questions