top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

How to find all possible subset of a set?

+3 votes
298 views

write a program and please explain the logic with example.

posted Apr 4, 2016 by Shahsikant Dwivedi

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

+1 vote

Program:

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

void printPowerSet(char *set, int set_size)
{
    /*set_size of power set of a set with set_size
      n is (2**n -1)*/
    unsigned int pow_set_size = pow(2, set_size);
    int counter, 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*/
int main()
{
    char set[] = {'a','b','c'};
    printPowerSet(set, 3);

    getchar();
    return 0;
}

Time Complexity: O(n2^n)

answer Apr 5, 2016 by Manikandan J
I did not understand logic of "if(counter & (1<<j))" little explanation would be helpful.
Similar Questions
+5 votes

Given a staircase with N steps, you can go up with 1 or 2 or 3 steps each time. Output all possible way you go from bottom to top.

For example:

N = 3

Output :
1 1 1
1 2
2 1
3

N = 4

Output:
1 1 1 1
1 2 1
1 1 2
2 1 1
3 1
1 3
2 2

+2 votes

Input:
arr = {'a', 'b'}, length = 3

Output:
aaa
aab
aba
abb
baa
bab
bba
bbb

...