• 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

Printing each word reverse in string

Check a String is SUBSEQUENCE of another String Find Minimum length for that ( DNA Matching )

LeetCode: Container With Most Water

Generate largest number arranging a no. of given non negative integer numbers

Find Percentage of Words matching in Two Strings

Max Sum in circularly situated Values

Count Possible Decodings of a given Digit Sequence

FizzBuzz Solution C C++

The Magic HackerEarth Nirvana solutions Hiring Challenge

strtok()

Subset Sum Problem Dynamic programming

Common Ancestor in a Binary Tree or Binary Search Tree

Find if two rectangles overlap

How strtok() Works

1014 Practice Question of New GRE – Princeton

Find loop in Singly linked list

SAP Hiring Off-Campus General Aptitude

Binary Tree in Java

Printing Longest Common Subsequence

Search element in a matrix with all rows and columns in sorted order

Closed Parentheses checker

Convert Decimal to Roman numbers / Romanizer HackerEarth Code

Maximum size of square sub matrix with all 1’s in a binary matrix

Trie Dictionary

C++ OOPs Part1

flattens 2 D linked list to a single sorted link list

robot standing at first cell of an M*N matrix. It can move only in two directions, right and down. In how many ways, it can reach to the last cell i.e. (M, N) Code it

Print vertical sum of all the axis in the given binary tree

Given a sorted array and a number x, find the pair in array whose sum is closest to x

Connect n ropes with minimum cost

Copyright © 2025 · Genesis Framework · WordPress · Log in