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)