Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Print All the Subsets of a Given Set (Power Set)

Objec­tive: Given a set of num­bers, print all the poss­si­ble sub­sets of it includ­ing empty set.

Power Set: In math­e­mat­ics, Pow­er­Set of any given set S, PS(S) is set of all sub­sets of S includ­ing empty set.
Exam­ple:

 S ={1,2,3}

PS(S): {{ᵩ}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

Approach:

Solu­tion to this prob­lem is sim­i­lar to — Print All Com­bi­na­tions of sub­set of size K from Given Array

  • Cre­ate an binary array of the same size as the given array.
  • Now for every inte­ger we have two options, whether to select it or ignore it.
  • Now if we select it, we will put 1 in the boolean array at the cor­re­spond­ing index or if we ignore it, put 0 at that index.
  • Say you have a vari­able called x, which rep­re­sents the cur­rent index at the given array.
  • Make x = 0 ( ignor­ing xth index) and x = 1( select­ing xth index) and make recur­sive

Code:


Out­put:

{Empty} {3}  {2}  {23}  {1}  {13}  {12}  {123}  

You may also like...