Power Set Geeks For Geeks

 Problem Link

https://practice.geeksforgeeks.org/problems/power-set4302/1/

Solution:

 ArrayList<String>aa=new ArrayList<String>();

        StringBuilder sb=new StringBuilder();

        for(int i=01;i<(int)Math.pow(2,s.length());i++){

            for(int j=0;j<s.length();j++){

                if((i&(1<<j))!=0){

                    sb.append(s.charAt(j));

                }

                

            }

            aa.add(sb.toString());

            sb.setLength(0);

        }

       

        Collections.sort(aa);

        

        return aa;

TIME COMPLEXITY:O(N^2)[GFG Time:1.9/3.9]

SPACE COMPLEXITY: O(1)

AUXILLARY SPACE: O(2*N)

TOTAL TEST CASES:90

APPROACH:

1.Here we will use binary representation to store characters of the string. Imagine it as 

for string abc

for index 0 it is c for 1 it is b and for 2 it is a.

In map form:

0->a 

1->b

2->c

2. Now we know that the maximum powerset can be 2^n. So for the 2^n powerset, there will be different 2^n 

combination of 0 and 1.

if the string is abc then

000 ->0

001 ->a

010 ->b

011 ->ab

100 ->c

101 ->ac

110 ->bc

111 ->abc

3. Following the same approach

 a)We will traverse up to 2^n and (using i)

b)For each value of i we find out the binary string representing 1

    b.1)Now traverse the binary string and if we get any set bit then we will append that corresponding character value (present in the given string).

    b.2)Traversal of the string will be from LSB to MSB. For that reason only we do the right shift of bits of number continuously.

    b.3)As the inner loop traversal is finished we store that value in ArrayList.

c) Now we got our all possible combinations in ArrayList. But in question solution is expected to be in sorted order. So for that only we do Collections. sort(aa).

d) return aa.

{Since the traversal of the string is from LSB to MSB therefore we are taking string values in that order. Means

For abc, if the set bit index is=0 then the value will be a not c.

If we take c then the answer will be in reverse order.

ex for 111 it will be cba but it should be abc.

That's why we follow the same order of character as present in the string and also assign each character with that particular index that is present in the original string.

ex for abc 0 for a 1 for b and 2 for c.

}

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"