Finding all the subsets of a given set

The total number of subsets of any given set is equal to 2^ (no. of elements in the set). Given a set S = {a,b,c,d}, the task is to find all the subsets of a set which are :

{}, {a} , {b}, {c}, {d}, {a,b}, {a,c}, {a,d}, {b,c}, {b,d}, {c,d}, {a,b,c}, {a,b,d}, {a,c,d}, {b,c,d}, {a,b,c,d}.

Now printing these subsets might seem tough as you might think to apply recursion or back tracing or play with pointers but if we carefully notice it is nothing but binary numbers from 0 to 15 which can be shown as below:

0000

{}

0001

{a}
0010 {b}
0011 {a,b}
0100 {c}
0101 {a,c}
0110 {b,c}
0111 {a,b,c}
1000 {d}
1001 {a,d}
1010 {b,d}
1011 {a,b,d}
1100 {c,d}
1101 {a,c,d}
1110 {b,c,d}
1111 {a,b,c,d}

Starting from right, 1 at ith position shows that the ith element of the set is present as 0 shows that the element is absent. Therefore what we have to do is just generate the binary numbers from 0 to 2^n – 1, where n is the length of the set or the numbers of elements in the set.

Here is Java code I wrote for this problem:

import java.io.IOException;

import java.util.Scanner;

public class Main{

public static void main(String[] args)throws IOException{

Scanner sc = new Scanner(System.in);

System.out.println(“Enter the number of elements in the set: “);

int N = sc.nextInt();

int[] sequence = new int[N];

System.out.println(“Enter the elements”);

for (int i = 0; i < N; i++)

sequence[i] = sc.nextInt();

for (int i = 0; i < (1<<N); i++){ //1<

System.out.print(“{ “);

for (int j = 0; j < N; j++)

if ((i & (1 << j)) > 0){   //(1<<j) is a number with jth bit 1 so when we ‘and’ them with the subset number we get which numbers are present in tht subset and which are not

System.out.print(sequence[j] + ” “);

}

System.out.println(“}”);

}

sc.close();

}

}

This question is frequently asked in interviews of big companies like amazon, flipkart, etc so should have a good command on its concept and the application of the concept.

For any doubts you can contact me at 201301151@daiict.ac.in or message me on facebook(https://www.facebook.com/nikhil.tekwani.18)