# Generate Powerset of a Set in Java

Write a program to generate Powerset of a Set in Java. A power set of set S is the set of all possible subsets of S, including the empty set and S itself.

For example, for set {a, b, c}, the subsets are:

• {} (empty set)
• {a}
• {b}
• {c}
• {a, b}
• {a, c}
• {b, c}
• {a, b, c}

and hence the power set of S is {{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.

Simplest solution is to use Guava library. The `powerSet()` method provided by Sets class calculates the set of all possible subsets of specified set.

Output:

[]
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]

Another approach to find Powerset is to generate all binary numbers between 0 to 2n-1 where n is the size of the specified set. For instance, for set {a, b, c}, we generate binary numbers from 0 to 23-1 and for each number generated, the correspoding set can be found by considering set bits in the number as shown below:

• 0 = 000 = {}
• 1 = 001 = {c}
• 2 = 010 = {b}
• 3 = 011 = {b, c}
• 4 = 100 = {a}
• 5 = 101 = {a, c}
• 6 = 110 = {a, b}
• 7 = 111 = {a, b, c}

Output:

[]
[1]
[2]
[1, 2]

References: https://en.wikipedia.org/wiki/Power_set

(2 votes, average: 5.00 out of 5)