Subset Generation Using Bits

Introduction to Subset Generation:

Subset generation using bits is a technique to generate all possible subsets of a set. It leverages the binary representation of numbers to represent the inclusion or exclusion of each element in the set.

Concept and Approach:

For a set with n elements, there are 2ⁿ possible subsets. Each subset can be represented by a binary number where each bit indicates whether an element is included (1) or excluded (0) in the subset.

Example 1: Subset Generation for {a, b}:

The set {a, b} has 2² = 4 subsets. We use binary numbers from 00 to 11 to represent them.

      import java.util.*;
      class SubsetExample {
        public static void main(String args[]) {
          char[] set = {'a', 'b'};
          int n = set.length;
          for (int i = 0; i < (1 << n); i++) {
            System.out.print("{ ");
            for (int j = 0; j < n; j++) {
              if ((i & (1 << j)) > 0) {
                System.out.print(set[j] + " ");
              }
            }
            System.out.println("}");
          }
        }
      }
      

{ }
{ a }
{ b }
{ a b }

Example 2: Subset Generation for {1, 2, 3}:

For the set {1, 2, 3}, we have 2³ = 8 subsets. Each subset corresponds to a binary number from 000 to 111.

      import java.util.*;
      class SubsetExample {
        public static void main(String args[]) {
          int[] set = {1, 2, 3};
          int n = set.length;
          for (int i = 0; i < (1 << n); i++) {
            System.out.print("{ ");
            for (int j = 0; j < n; j++) {
              if ((i & (1 << j)) > 0) {
                System.out.print(set[j] + " ");
              }
            }
            System.out.println("}");
          }
        }
      }
      

{ }
{ 1 }
{ 2 }
{ 1 2 }
{ 3 }
{ 1 3 }
{ 2 3 }
{ 1 2 3 }

Example 3: Subset Generation for {x, y, z, w}:

The set {x, y, z, w} results in 2⁴ = 16 subsets. Binary numbers from 0000 to 1111 represent these subsets.

      import java.util.*;
      class SubsetExample {
        public static void main(String args[]) {
          char[] set = {'x', 'y', 'z', 'w'};
          int n = set.length;
          for (int i = 0; i < (1 << n); i++) {
            System.out.print("{ ");
            for (int j = 0; j < n; j++) {
              if ((i & (1 << j)) > 0) {
                System.out.print(set[j] + " ");
              }
            }
            System.out.println("}");
          }
        }
      }
      

{ }
{ x }
{ y }
{ x y }
{ z }
{ x z }
{ y z }
{ x y z }
{ w }
{ x w }
{ y w }
{ x y w }
{ z w }
{ x z w }
{ y z w }
{ x y z w }

Example 4: Subset Generation for {10, 20}:

For the set {10, 20}, the number of subsets is 2² = 4. Here, binary numbers 00 to 11 are used.

      import java.util.*;
      class SubsetExample {
        public static void main(String args[]) {
          int[] set = {10, 20};
          int n = set.length;
          for (int i = 0; i < (1 << n); i++) {
            System.out.print("{ ");
            for (int j = 0; j < n; j++) {
              if ((i & (1 << j)) > 0) {
                System.out.print(set[j] + " ");
              }
            }
            System.out.println("}");
          }
        }
      }
      

{ }
{ 10 }
{ 20 }
{ 10 20 }

Example 5: Subset Generation for {red, green, blue}:

The set {red, green, blue} has 2³ = 8 subsets, represented by binary numbers 000 to 111.

      import java.util.*;
      class SubsetExample {
        public static void main(String args[]) {
          String[] set = {"red", "green", "blue"};
          int n = set.length;
          for (int i = 0; i < (1 << n); i++) {
            System.out.print("{ ");
            for (int j = 0; j < n; j++) {
              if ((i & (1 << j)) > 0) {
                System.out.print(set[j] + " ");
              }
            }
            System.out.println("}");
          }
        }
      }
      

{ }
{ red }
{ green }
{ red green }
{ blue }
{ red blue }
{ green blue }
{ red green blue }