• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Print Power Set of a Set

April 18, 2015 by Dhaval Dave

Print Power Set of a Set of character.

Power Set Power set P(S) of a set S is the set of all subsets of S. For example S = {a, b, c} then P(s) = {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}}.

If S has n elements in it then P(s) will have 2^n elements

 

Method 1:

Input: Set[], set_size
1. Get the size of power set
    powet_set_size = pow(2, set_size)
2  Loop for counter from 0 to pow_set_size
     (a) Loop for i = 0 to set_size
          (i) If ith bit in counter is set
               Print ith element from set for this subset
     (b) Print seperator for subsets i.e., newline

#include <stdio.h>
#include <math.h>
 

voidprintPowerSet(char*set, intset_size)
{
    /*set_size of power set of a set with set_size
      n is (2**n -1)*/
    unsigned intpow_set_size = pow(2, set_size);
    intcounter, j;
    /*Run from counter 000..0 to 111..1*/
    for(counter = 0; counter < pow_set_size; counter++)
    {
      for(j = 0; j < set_size; j++)
       {
          /* Check if jth bit in the counter is set
             If set then pront jth element from set */
          if(counter & (1<<j))
            printf("%c", set[j]);
       }
       printf("n");
    }
}
/*Driver program to test printPowerSet*/
intmain()
{
    charset[] = {'a','b','c'};
    printPowerSet(set, 3);
    getchar();
    return0;
}

Method 2:  We can use Recursion and with understanding of Binary Tree , we can format it.
Example : 

                   {a,b,c} print set= abc
                    / \ 
                   /   \ 
                  /     \ 
               {a,b}    {b,c}  print set = ab,bc
                /\        /\ 
               /  \      /  \ 
              {a}  {b} {b}  {c} print set
          
void printPowerSet(char *set, int l , int h , int size)
{
    int i=l;
    for(i=l;i<=h;i++){printf("%c",set[i]);}
     printf("n");
     if(l+1 < size){ 
          printPowerSet(set,l+1,h,size); 
     } 
     if(h-1 >= 0 ){
            printPowerSet(set,l,h-1,size);
     }
}//printpowerset

int main(void) {
char set[] = {'a','b','c','d'};
printPowerSet(set,0,3,4 );
 
getchar();
 
return 0;
}

I have run it here…
http://ideone.com/e.js/faEPpM

 

 

 

 

Similar Articles

Filed Under: Adobe Interview Questions, Hacker Earth Questions, Interview Questions, problem Tagged With: Array, Recursion, string

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Right view of Binary tree

Python Dictionaries

Find and print longest consecutive number sequence in a given sequence in O(n)

CodeChef’ RRCOPY

Spanning Tree

HackeEarth Flipkart’s Drone

Trie Dictionary

Facebook Interview Question : Interleave List

Find min element in Sorted Rotated Array (With Duplicates)

Get Minimum element in O(1) from input numbers or Stack

Best Java Book | Top Java Programming Book for Beginners

Printing each word reverse in string

The greedy coins game Dynamic Programming

BFS (Breath First Search)

N Petrol bunks or City arranged in circle. You have Fuel and distance between petrol bunks. Is it possible to find starting point so that we can travel all Petrol Bunks

LeetCode : Word Search

Skiing on Mountains Matrix

Implement a generic binary search algorithm for Integer Double String etc

FizzBuzz Solution C C++

Calculate price of parking from parking start end time prices

Minimum insertions to form a palindrome

Code Chef PRGIFT Solution

‘N’ Story Building, with 1,2,3 steps how many ways can a person reach top of building.

Find Pythagorean Triplets in an array in O(N)

Possible sizes of bus to carry n groups of friends

Reversal of LinkedList

Python Array String

Microsoft BING Interview Experience

LeetCode: Binary Tree Maximum Path Sum

TicTacToe Game As Asked in Flipkart

Copyright © 2025 · Genesis Framework · WordPress · Log in