Algorithms and Data Structures : Part 4.2 String : Substring : Subset : Permutation : Combination

So in the last post we have seen , how to generate all possible substring for a given string.


That  will solve lot of question on string.


Here we will see how to generate all possible SUBSETS, since a lot of questions, where we have to pick for N numbers ...any combination such that it satisfies a given condition can be solved using this.




Ex : Given 6 coins of different denomination, find how we can have 3 coins where sum of these 3 is 20 bucks.


or any number of coins such that sum is 15 bucks.


In case of SUBSTRING, maximum possible SUBSTRING where for STRING of length N is N*(N+1)/2


In case of SUBSETS, it is 2^N....since either a element is in subset or not in subset.


so given {1,2,3}  ...we can have  {}, {1},{2}, {3},{1,2},{2,3},{1,3},{1,2,3}.....2^3 = 8 elements.


So if we assign 1 bit to each element, we can see that for  8 elements ...the binary representation will be (starting from 0)


0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1


Now if you pay close attention we can see , if we think of these bits are element position, and treat 1 as including that element in subset and 0 as not....we can have all the elements


So


0 0 0
0 0 3
0 2 0
0 2 3
1 0 0
1 0 3
1 2 0
1 2 3


So in our algorithm , if we have 3 elements we have to run a loop from  index=0 till index < 2^3


and take binary representation of index...and then see at which position we have 1 , then include those in our sets.


Code :  https://ideone.com/0WQgqM




Now lets see some time complexity and other points


1) When I run the above code for SET of length  < 12, it is fast...but for set values more than 12 , you can see it started to take more time.


2) We are running our loop  less than 2^N....NEED TO TAKE CARE, that the  index type satisfy such a big number...whether you will take INT or LONG.


3) What if our question says SET of 3 numbers or set of 4 numbers.


So now even if from a given set of  say  6 numbers, we have to select 3 numbers satisfying some condition. What is much better running loop till 2^6  and then selecting all subset having 3 numbers  or directly generating set of 3 numbers.


To select 3 numbers from 6 numbers, we have  6C3 =  6!/3!*3! =  20


So if we can generate combination directly we can solve this problem in 20 iteration , whereas with SUBSET we have to go for 64 iteration.


So now we see how to generate combination in next post.