Power Set

Power Set Power set P(S) of a set S is the set of all subsets of S. For example S = {a, b, c} then P(s) = {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}}.

If S has n elements in it then P(s) will have 2^n elements

Algorithm:

Input: Set[], set_size
1. Get the size of power set
powet_set_size = pow(2, set_size)
2  Loop for counter from 0 to pow_set_size
(a) Loop for i = 0 to set_size
(i) If ith bit in counter is set
Print ith element from set for this subset
(b) Print seperator for subsets i.e., newline

Example:

Set  = [a,b,c]
power_set_size = pow(2, 3) = 8
Run for binary counter = 000 to 111

Value of Counter            Subset
000                    -> Empty set
001                    -> a
010                    -> b
011                    -> ab
100                    -> c
101                    -> ac
110                    -> bc
111                    -> abc

Program:

C++

 // C++ Program of above approach #include #include using namespace std;    class gfg {        public: void printPowerSet(char *set, int set_size) {     /*set_size of power set of a set with set_size     n is (2**n -1)*/     unsigned int pow_set_size = pow(2, set_size);     int counter, j;        /*Run from counter 000..0 to 111..1*/     for(counter = 0; counter < pow_set_size; counter++)     {     for(j = 0; j < set_size; j++)     {         /* Check if jth bit in the counter is set             If set then print jth element from set */         if(counter & (1 << j))             cout << set[j];     }     cout << endl;     } } };    /*Driver code*/ int main() {     gfg g;     char set[] = {'a','b','c'};     g.printPowerSet(set, 3);     return 0; }    // This code is contributed by SoM15242

/div>

C

 #include #include    void printPowerSet(char *set, int set_size) {     /*set_size of power set of a set with set_size       n is (2**n -1)*/     unsigned int pow_set_size = pow(2, set_size);     int counter, j;        /*Run from counter 000..0 to 111..1*/     for(counter = 0; counter < pow_set_size; counter++)     {       for(j = 0; j < set_size; j++)        {           /* Check if jth bit in the counter is set              If set then print jth element from set */           if(counter & (1<

Java

 // Java program for power set import java .io.*;    public class GFG {            static void printPowerSet(char []set,                             int set_size)     {                    /*set_size of power set of a set         with set_size n is (2**n -1)*/         long pow_set_size =              (long)Math.pow(2, set_size);         int counter, j;                /*Run from counter 000..0 to         111..1*/         for(counter = 0; counter <                  pow_set_size; counter++)         {             for(j = 0; j < set_size; j++)             {                 /* Check if jth bit in the                  counter is set If set then                  print jth element from set */                 if((counter & (1 << j)) > 0)                     System.out.print(set[j]);             }                            System.out.println();         }     }            // Driver program to test printPowerSet     public static void main (String[] args)     {         char []set = {'a', 'b', 'c'};         printPowerSet(set, 3);     } }    // This code is contributed by anuj_67.

Python3

 # python3 program for power set    import math;    def printPowerSet(set,set_size):            # set_size of power set of a set     # with set_size n is (2**n -1)     pow_set_size = (int) (math.pow(2, set_size));     counter = 0;     j = 0;            # Run from counter 000..0 to 111..1     for counter in range(0, pow_set_size):         for j in range(0, set_size):                            # Check if jth bit in the              # counter is set If set then              # print jth element from set              if((counter & (1 << j)) > 0):                 print(set[j], end = "");         print("");    # Driver program to test printPowerSet set = ['a', 'b', 'c']; printPowerSet(set, 3);    # This code is contributed by mits.

C#

 // C# program for power set using System;    class GFG {            static void printPowerSet(char []set,                             int set_size)     {         /*set_size of power set of a set         with set_size n is (2**n -1)*/         uint pow_set_size =                (uint)Math.Pow(2, set_size);         int counter, j;                /*Run from counter 000..0 to         111..1*/         for(counter = 0; counter <                     pow_set_size; counter++)         {             for(j = 0; j < set_size; j++)             {                 /* Check if jth bit in the                  counter is set If set then                  print jth element from set */                 if((counter & (1 << j)) > 0)                     Console.Write(set[j]);             }                            Console.WriteLine();         }     }            // Driver program to test printPowerSet     public static void Main ()     {         char []set = {'a', 'b', 'c'};         printPowerSet(set, 3);     } }    // This code is contributed by anuj_67.

PHP



Output :

a
b
ab
c
ac
bc
abc

Time Complexity: O(n2^n)

Recursive program to generate power set

Refer Power Set in Java for implementation in Java and more methods to print power set.

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

If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to [email protected] See your article appearing on the GeeksforGeeks main page and help other Geeks.

tags:

Mathematical Mathematical