Get this book -> Problems on Array: For Interviews and Competitive Programming

In this article, we have explored what is the meaning of Power Set of String and the algorithm to generate Power Set of String in Lexicographic order.

## Table of contents

- Power Set
- Lexicographic order
- What is Power set of string in Lexicographic order?
- Algorithm
- Complextiy

## Power Set

We are all familiar with term "SET" at somewhere, probably in set theory (or in mathematics).

What is set? The answer is "It is a collection of well defined unordered distinct objects".

Example:

- The collection of all tall boys in the class.

It is not a set, because we do not know that which height we can treat as tall. - The collection of all tall boys whose height is greater or equal to 165cm in the class.

It is a set.

## Question

#### Which of the following is set?

What is Power Set ? "It is a collection of all possible subsets of a given set is called Power Set". The power set of 'A' is denoted by P(A).

Example:

- Given set S: {a, b}

Then Power set P(S): {" ", a, b, ab}

Note: Taking " " as NULLSET. - Set S: {a, b, c}

Power set P(S): {" ", a, b, c, ab, ac, bc, abc}

Now, Formula to find the number of elements in Power Set,

Lets take Set A: {a, b, c}, Number of elements in Set 'A' are 3, and the power set P(A): {" ", a, b, c, ab, ac, bc, abc} and Number of elements in P(A) are C(3,0) + C(3,1) + C(3,2) + C(3,3) = 8.

Therefore, If Number of elements in Set A are 'N', then Number of elements in Power Set P(A) are ( C(N,0) + C(N,1) + C(N,2) + . . . + C(N,N) ) = 2^N.

## Question

#### Which of the option is the power set of set A= { {1}, {2,3} }?

## Lexicographic order

Lexicographic order is a way of ordering words in alphabatical order based on their components alphabets. It is also known as Dictionary Order.

Example: algorithm, worst, average, best

Lexicographic order: algorithm, average, best, worst

## Power Set of String in Lexicographic order

In this, we are given a string S, we have to find the power set of this string in lexicographical order and print them.

Example:

Say S: {a, b, c}

Power set P(S): {" ", a, b, c, ab, ac, bc, abc}

Output should look like: [ " ", a, ab, abc, ac, b, bc, c ]

### Algorithm

###### Using Recursion

Arguments passed in Power set function are:

- S: Given input String
- Size: Length of string S
- pos: Index in current permutation
- sset: Stores current Permutation Subset

Begin power-set

- power-set function is having four arguments given input string 'S', size of S, current position "pos", and subset string "sset" which will stores subset.
- Base condition: if current pos is equal to the size of given string S then return.
- print the subset string.
- Run a for-loop for i: current pos +1 to size of give string.
- concatenate the element of S[i] into subset string(sset).
- Now call the power-set function by giving S, size, i+1, sset
- remove one element from the last of sset.

- return

End power-set

```
Using Recursion method
power-set(S, size, pos, sset){
if(pos is equals to the size)
then
return
end if
print string sset
for i: pos + 1 to size
concatenate the element of S[i] into sset
power-set(S, size, i+1, sset)
remove one(1) elements from string sset from end
end for
return
}
```

###### Code

```
#include <bits/stdc++.h>
using namespace std;
//-----------Power-Set Function---------------//
void power_set(string S, int n, int pos = -1, string sset = "") {
//Base case condition
if (pos == n)
return;
//Print string in Subset
cout<<sset<<"\n";
for (int i = pos + 1; i < n; i++) {
sset+= S[i];
power_set(S, n, i, sset);
//BackTracking
sset = sset.erase(sset.size() - 1);
}
return;
}
//----------Remove Duplicate Elements--------//
string duplicate(string s){
if(s.size()==0){
return "";
}
string x="";
int n=s.size(),i=0;
x+=s[0];
for(int j=1;j<n;j++){
if(x[i]!=s[j]){
i++;
x+=s[j];
}
}
return x;
}
//-----------Driver Function---------------//
int main() {
string S;
cout<<"Enter string: \n";
cin>>S;
cout<<"Power Set of the string '"<<S<<"' is :\n";
//sort the elements
sort(S.begin(),S.end());
//call duplicate() to remove duplicate elements
S=duplicate(S);
//calling power-set function
power_set(S, S.size());
return 0;
}
```

###### Output

```
Enter string:
merge
Power Set of the string 'merge' is :
e
eg
egm
egmr
egr
em
emr
er
g
gm
gmr
gr
m
mr
r
```

###### Using Iteration

Keep some logical things in mind, given below:

- '&'(Bitwise And) works as it takes two operands and does And on every bit of two numbers.

Example: Take operand-1 as 2: 010(in binary) and operand-2 as 6: 110(in binary). Now, take these two operands and do bitwise and operation i.e. (110)&(010)= 10 (in decimal it is '2'). - '<<'(Bitwise left shift) works as it shifts the bit of first operand the specified number of bits.

Example: if x=2(10 in binary), then y = x<<2 = 8(1000 in binary).

Begin power-set(s)

- Where s: given string
- take variable to store elements of power set, lets say sub
- for i: 0 to 2^(length of s)
- take a string variable to store current permutation subset, lets say sset
- for j:0 to (length of s)
- condition: if(jth bit of i is set"1"), then insert the element on s[j] into sset

- insert the sset into sub

- sort the elements of sub
- Now print all the elements of sub

End power-set

```
power-set(s, length)
take a variable which will store all the string of power set, say sub
take a variable, lets say power, which will run up 2^length
for i:0 to power
take a string variable say sset to store current permutation subset
for j:0 to length
condition: if(i & (1<<j))
then insert s[j] into sset
end for
insert the sset into sub
end for
sort the sub
print the elements of sub using loop
return
```

Where s: given input string

length: size of String s

###### Code

```
#include <bits/stdc++.h>
using namespace std;
//-----------Power-Set Function---------------//
void power_set(string s,int n) {
vector<string> sub;
int power;
power=pow(2,n);
for(int i=0;i<power;i++){
string sset="";
for(int j=0;j<n;j++){
if(i & (1<<j)){
sset+=s[j];
}
}
//push the subsequence into sub
sub.push_back(sset);
}
//sort the vector string
sort(sub.begin(),sub.end());
//print the Power-set
int len=sub.size();
for(int i=0;i<len;i++){
cout<<sub[i]<<endl;
}
return;
}
//----------Remove Duplicate Elements--------//
string duplicate(string s){
if(s.size()==0){
return "";
}
string x="";
int n=s.size(),i=0;
x+=s[0];
for(int j=1;j<n;j++){
if(x[i]!=s[j]){
i++;
x+=s[j];
}
}
return x;
}
//-----------Driver Function---------------//
int main() {
string S;
cout<<"Enter string: \n";
cin>>S;
cout<<"Power Set of the string '"<<S<<"' is :\n";
//sort the elements
sort(S.begin(),S.end());
//call duplicate() to remove duplicate elements
S=duplicate(S);
//calling power-set function
power_set(S, S.size());
return 0;
}
```

###### OUTPUT

```
Enter string:
algo
Power Set of the string 'algo' is :
a
ag
agl
aglo
ago
al
alo
ao
g
gl
glo
go
l
lo
o
```

### Complexity

###### Using Recursion

Time Complexity: O(N*(2^N)), N is the size of the given input string and 2^N elements in power-set.

Space Complexity: O(N), N is the size of string.

In the worst case scenario, the depth of the recursion tree would be āNā. Hence, the overall space complexity due to the recursion call stack is O(N).

###### Using Iterartion

Time Complexity: O(N*(2^N)), N is the size of the given input string and 2^N elements in power-set.

Space Complexity: O(1), constant space complexity.