Power Set of a Set using C, C++, Java and Python

---

❮ Previous    Next ❯

---

---

Objective

To write a program in C, C++, Java and Python to create a set and perform the Power Set operation on the set.

---

Theory

The Power Set of a set A is represented by:

P(A)

It is the set containing all possible subsets of Set A.

If a set contains n elements, then its Power Set contains:

2ⁿ subsets

---

Example

Consider the set:

A = {1, 2, 3}

The Power Set contains all possible subsets of A:

P(A) = { ∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }

Since Set A contains 3 elements:

2³ = 8

Therefore, the Power Set contains 8 subsets.

---

Important Points

• The Power Set contains the empty set.
• The Power Set contains the original set.
• If A contains n elements, P(A) contains 2ⁿ subsets.
• The Power Set is itself a set.
• The number of subsets grows exponentially with the number of elements.

---

Bitmask Concept

One efficient way to generate a Power Set is by using the bitmask technique. For a set containing n elements, we need to generate numbers from:

0 to 2ⁿ − 1

Each binary number represents one possible subset. For example, consider:

A = {1, 2, 3}

Binary	Selected Elements	Subset
000	None	∅
001	1	{1}
010	2	{2}
011	1, 2	{1,2}
100	3	{3}
101	1, 3	{1,3}
110	2, 3	{2,3}
111	1, 2, 3	{1,2,3}

---

Algorithm

1. Start.
2. Read the number of elements n.
3. Read the elements of the set.
4. Calculate 2ⁿ.
5. Generate numbers from 0 to 2ⁿ − 1.
6. For each number, examine its binary representation.
7. If a particular bit is 1, include the corresponding element in the subset.
8. Display the generated subset.
9. Repeat until all 2ⁿ subsets have been generated.
10. Stop.

---

Flowchart

---

Example

Number of Elements	Number of Subsets
1	2¹ = 2
2	2² = 4
3	2³ = 8
4	2⁴ = 16
5	2⁵ = 32

---

C Program

The following C program generates the Power Set using the bitmask technique.

/* C Program to Generate Power Set */

#include <stdio.h>

int main()
{
    int set[20];
    int n;
    int i, j;
    int total;

    printf("Enter number of elements in the set: ");
    scanf("%d", &n);

    printf("Enter elements of the set:\n");

    for(i = 0; i < n; i++)
    {
        scanf("%d", &set[i]);
    }

    total = 1 << n;

    printf("\nPower Set:\n");

    for(i = 0; i < total; i++)
    {
        printf("{ ");

        for(j = 0; j < n; j++)
        {
            if(i & (1 << j))
            {
                printf("%d ", set[j]);
            }
        }

        printf("}\n");
    }

    return 0;
}

---

Sample Output (C)

Enter number of elements in the set: 3

Enter elements of the set:
1 2 3

Power Set:
{ }
{ 1 }
{ 2 }
{ 1 2 }
{ 3 }
{ 1 3 }
{ 2 3 }
{ 1 2 3 }

---

How the C Program Works

1. The elements of the set are stored in an array.
2. The program calculates 2ⁿ using the left-shift operation.
3. Each number from 0 to 2ⁿ − 1 represents one subset.
4. Each bit is checked using the bitwise AND operator.
5. If a bit is 1, the corresponding element is included.
6. If a bit is 0, the corresponding element is excluded.
7. All possible subsets are therefore generated.

---

Understanding the Bitwise Operation

The expression:

i & (1 << j)

checks whether the j-th bit of i is set to 1. If the result is non-zero, the corresponding element is included in the subset.

---

C++ Program

/* C++ Program to Generate Power Set */

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;

    cout << "Enter number of elements in the set: ";
    cin >> n;

    vector<int> set(n);

    cout << "Enter elements of the set:\n";

    for(int i = 0; i < n; i++)
    {
        cin >> set[i];
    }

    int total = 1 << n;

    cout << "\nPower Set:\n";

    for(int i = 0; i < total; i++)
    {
        cout << "{ ";

        for(int j = 0; j < n; j++)
        {
            if(i & (1 << j))
            {
                cout << set[j] << " ";
            }
        }

        cout << "}\n";
    }

    return 0;
}

---

Sample Output (C++)

Enter number of elements in the set: 3

Enter elements of the set:
1 2 3

Power Set:
{ }
{ 1 }
{ 2 }
{ 1 2 }
{ 3 }
{ 1 3 }
{ 2 3 }
{ 1 2 3 }

---

Java Program

The following Java program generates all subsets using the bitmask technique.

/* Java Program to Generate Power Set */

import java.util.Scanner;

public class PowerSet
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);

        System.out.print("Enter number of elements in the set: ");
        int n = sc.nextInt();

        int[] set = new int[n];

        System.out.println("Enter elements of the set:");

        for(int i = 0; i < n; i++)
        {
            set[i] = sc.nextInt();
        }

        int total = 1 << n;

        System.out.println("\nPower Set:");

        for(int i = 0; i < total; i++)
        {
            System.out.print("{ ");

            for(int j = 0; j < n; j++)
            {
                if((i & (1 << j)) != 0)
                {
                    System.out.print(set[j] + " ");
                }
            }

            System.out.println("}");
        }

        sc.close();
    }
}

---

Sample Output (Java)

Enter number of elements in the set: 3

Enter elements of the set:
1 2 3

Power Set:
{ }
{ 1 }
{ 2 }
{ 1 2 }
{ 3 }
{ 1 3 }
{ 2 3 }
{ 1 2 3 }

---

Python Program

Python can generate the Power Set using the same bitmask concept.

# Python Program to Generate Power Set

n = int(input("Enter number of elements in the set: "))

elements = []

print("Enter elements of the set:")

for i in range(n):

    elements.append(int(input()))

total = 1 << n

print("\nPower Set:")

for i in range(total):

    subset = []

    for j in range(n):

        if i & (1 << j):

            subset.append(elements[j])

    print(subset)

---

Sample Output (Python)

Enter number of elements in the set: 3

Enter elements of the set:
1
2
3

Power Set:
[]
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]

---

Python Using itertools

Python also provides a convenient way to generate combinations using the itertools module.

# Python Program to Generate Power Set using itertools

from itertools import combinations

A = {1, 2, 3}

power_set = []

for r in range(len(A) + 1):

    for subset in combinations(A, r):

        power_set.append(set(subset))

print("Set A =", A)

print("Power Set:")

for subset in power_set:

    print(subset)

---

Python Using a Simple Iterative Method

The Power Set can also be generated by starting with the empty set and repeatedly adding each element to all existing subsets.

# Python Program to Generate Power Set

A = [1, 2, 3]

power_set = [[]]

for element in A:

    new_subsets = []

    for subset in power_set:

        new_subsets.append(subset + [element])

    power_set = power_set + new_subsets

print("Set A =", A)

print("Power Set:")

for subset in power_set:

    print(subset)

---

Number of Subsets

For a set containing n elements, the number of subsets is:

2ⁿ

For example, for 4 elements:

2⁴ = 16

Therefore, a set containing four elements has exactly 16 subsets.

---

Dry Run

Consider the set:

A = {1, 2, 3}

Since the set contains three elements:

2³ = 8

Therefore, eight subsets will be generated.

Decimal	Binary	Selected Elements	Subset
0	000	None	∅
1	001	1	{1}
2	010	2	{2}
3	011	1, 2	{1,2}
4	100	3	{3}
5	101	1, 3	{1,3}
6	110	2, 3	{2,3}
7	111	1, 2, 3	{1,2,3}

---

Understanding the Bitmask

Suppose:

A = {1, 2, 3}

For the binary number 101:

• The first bit is 1 → include 1.
• The second bit is 0 → exclude 2.
• The third bit is 1 → include 3.

Therefore:

101 → {1,3}

This is the basic idea behind the bitmask algorithm.

---

Time Complexity

Operation	Complexity
Generate all subsets	O(n × 2ⁿ)

There are 2ⁿ subsets, and each subset may require checking up to n elements. Therefore, the overall time complexity is:

O(n × 2ⁿ)

---

Space Complexity

If the generated Power Set is stored, the space requirement can be considered:

O(n × 2ⁿ)

This is because there are 2ⁿ subsets and each subset can contain up to n elements.

---

Applications

• Combinatorial Problems
• Subset Sum Problems
• Dynamic Programming
• Backtracking
• Optimization Problems
• Combinatorial Search
• Feature Selection
• Machine Learning
• Database Query Processing
• Artificial Intelligence

---

Advantages

• Simple and systematic method for generating all subsets.
• Bitmask technique is easy to implement.
• Works efficiently for small sets.
• Useful in many combinatorial algorithms.
• Can be implemented in C, C++, Java and Python.

---

Disadvantages

• The number of subsets increases exponentially.
• Large sets require significant memory.
• Time complexity becomes very high for large values of n.
• Power Set generation is generally impractical for very large sets.

---

Important Properties of Power Set

• If A contains n elements, P(A) contains 2ⁿ elements.
• The empty set ∅ always belongs to P(A).
• The original set A always belongs to P(A).
• Every subset of A belongs to P(A).
• P(A) itself is a set.

---

Viva Questions

1. What is a Power Set?
2. How is Power Set represented?
3. How many subsets does a set containing n elements have?
4. What is the Power Set of {1,2}?
5. Does the Power Set contain the empty set?
6. Does the Power Set contain the original set?
7. What is the time complexity of generating a Power Set?
8. What is the bitmask technique?
9. Why are numbers from 0 to 2ⁿ − 1 used?
10. What does a bit value of 1 represent?

---

Frequently Asked Interview Questions

1. What is a Power Set?
   A Power Set is the set containing all possible subsets of a given set.


2. How many elements are present in the Power Set of a set containing n elements?
   The Power Set contains 2ⁿ elements.


3. What is the Power Set of {a,b}?
   P(A) = {∅, {a}, {b}, {a,b}}


4. Why does the Power Set contain 2ⁿ subsets?
   Each element has two possibilities: it can either be included in a subset or excluded from it. Therefore, for n elements there are 2 × 2 × ... × 2 = 2ⁿ possible subsets.


5. What is the time complexity of Power Set generation?
   The standard bitmask implementation takes O(n × 2ⁿ) time.


6. Why is Power Set generation considered exponential?
   Because the number of subsets doubles whenever one additional element is added to the original set.

---

Practice Questions

1. Write a C program to generate the Power Set of a set.
2. Write a C++ program to generate the Power Set.
3. Write a Java program to generate the Power Set.
4. Write a Python program to generate the Power Set.
5. Find the Power Set of {1,2}.
6. Find the Power Set of {a,b,c}.
7. How many subsets are present in the Power Set of a 5-element set?
8. Generate the Power Set without using built-in functions.
9. Explain the bitmask technique used for Power Set generation.
10. Determine the time and space complexity of Power Set generation.

---

---

Summary

The Power Set of a set is the set containing all possible subsets of that set. If a set contains n elements, its Power Set contains 2ⁿ subsets. For example, the Power Set of {1,2,3} contains eight subsets. In this experiment, the Power Set operation has been implemented using C, C++, Java and Python. The bitmask technique is used to systematically generate every possible subset. Since the number of subsets grows exponentially, the standard algorithm has a time complexity of O(n × 2ⁿ).

---

---

---

❮ Previous    Next ❯

---