Question

Write a static method called generateSubstrings that adds all subsets of the letters in its first argument to the ArrayList that is its second argument. For example,

Answer 1

FOLLOW THE COMMENTS IN CODE TO UNDERSTAND THE CODE BEHIND THE FUNCTION.

COMMENT IF YOU GO THROUGH ANY PROBLEM RELATED TO THE QUESTION AND MY SOURCE CODE

private static void generateSubstrings(String text,ArrayList<String> arrlist)
   {
       /* THIS PRIVATE FUNCTION ASSUMES THE FIRST ARHGUMENT TO
       BE A STRING AND THE SECOND AN ARRAYLIST TO WHICH ALL STRINGS
       IN THE FORM OF SUBSETS CAN BE ADDED TO IT*/
       /*
      
       To test the code I have used the extra indentation.
       Our idea is following
      
       We remove duplicates from the String text
      
       We find the total number of possibilities i.e 2 ^ length
       of the string without duplicates
      
       Run through each and every possibility.Our idea is that the
       binary no of the loop variable for each possibilities has one-to-one
       correspondence with the subset to be found. suppose that
       the string without duplicates is "abc" ane the loop variable is 5
       whose binary representation is 101 . In that case we will
       take the first element and last element of the string without duplicates
       i.e the place where '1' matches .we need to add the zeros
       before the binary_representation so as to match the length of the string without
       duplicates so that we can easily find the subset for
       that particular loop variable
       000 in this case is the empty set
       */
      
       //Remove duplicates from the string "text"
       String no_duplicates="";
       for(int i=0;i<text.length();i++)
       {
           boolean flag=true;
           for(int j=i+1;j<text.length();j++)
               if(text.charAt(j)==text.charAt(i))
                   flag=false;
           if(flag)
               no_duplicates=no_duplicates+text.charAt(i);
       }
      
       //Calculate no of possibilities
       int end_no=(int)Math.pow(2,no_duplicates.length());
      
       //The loop that adds the subsets in form of strings
       for(int i=0;i<end_no;i++)
       {
           String bin_no=Integer.toBinaryString(i);
           //Adding extra zeros
           int no_of_extra_zeros=no_duplicates.length()-bin_no.length();
           for(int j=0;j<no_of_extra_zeros;j++)
               bin_no="0"+bin_no;
          
          
           String generated_strings="";
           for(int j=0;j<bin_no.length();j++)
           {
               if (bin_no.charAt(j)=='1')
               generated_strings=generated_strings+no_duplicates.charAt(j);
           }
           arrlist.add(generated_strings);
       }
   }