Strategies & Mathematics behind various ways to generate subsequences/subsets of a string/array
The problem of generating all possible subsequences/subsets of a string/array is generally considered to be an easy problem asked in coding interviews.
There are several possible ways to approach this problem, but are we aware of why these methods give a correct solution?
Here, we will discuss why all these methods end up giving the same results .i.e. all possible subsequences of an array.
Method 1:- Using two calls of including or excluding the character(include-exclude strategy)
- Here each time, at each level of the recursive tree we have two choices for the element whether we may choose it to be a part of our answer or we may not.
- We explore both these possibilities and move deeper into the tree. Thus, we get our answers finally when our base case gets hit.
Suppose, we have to generate all the subsequences for the array arr[] = {1,2,3} . The Recursive tree is shown below for this example:-
Implementation in Java:-
public static int subsequence1(int arr[],int idx,String ans){
if(idx == arr.length)
{
System.out.println(ans);
return 1;
}
int count = 0;
count += subsequence1(arr,idx+1,ans); // exclude the element
count += subsequence1(arr,idx+1,ans+arr[idx]); // include the element
return count;
}
Method 2:- Using the Method of Combinations
- Here, we get our answers at each call in our recursive tree not only at the base case unlike Method 1.
Suppose, we have to generate all the subsequences for the array arr[] = {1,2,3} . The Recursive tree is shown below for this example:-
Total ways= 3C0 + 3C1 + 3C2 + 3C3 = 1 + 3 + 3 + 1 = 8 ways.
Implementation in Java:-
public static int subsequence2(int arr[],int idx,String ans){
System.out.println(ans);
int count = 0;
for (int i = idx; i < arr.length; i++)
{
count += subsequence2(arr, i + 1, ans + arr[i]);
}
return count+1;
}
Method 3:- Using Bit Manipulation
- Bit Manipulation can easily generate all the subsets of an array.
Consider an array of 3 elements. arr[] = {1,2,3}
Now, we need 3 bits, one bit for each element. 1 represents that the corresponding element is present in the subset, whereas 0 represents the corresponding element is not in the subset.
All the possible combinations of these 3 bits are written below:
0 = (000)2 = {}
1 = (001)2 = {c}
2 = (010)2 = {b}
3 = (011)2 = {b, c}
4 = (100)2 = {a}
5 = (101)2 = {a, c}
6 = (110)2 = {a, b}
7 = (111)2 = {a, b, c}
Implementation in Java:-
public static int subsequence3(int arr[]){
int count = 0;
int n = arr.length;
for(int i = 0;i < (1 << n); ++i)
{
count++;
for(int j = 0;j < n;++j){
if((i & (1 << j)) != 0)
System.out.print(arr[j]);
}
System.out.println();
}
return count;
}
Equation behind the same answers using these three methods:-
In the binomial expansion :-
(a+b)^n = nC0a^n. b⁰ + nC1 a^(n-1)b¹ + nC2a^(n-2)b² +…………….+nCna⁰b^n …… (1)
Now let a=b=1 in eq (1):-
(1+1)^n =2^n = nC0 + nC1 +nC2 +……..+ nCn …… (2)
Here if we observe then what we have is the number of subsets of size r taken from a set of n objects i.e array arr.
nC0 = 1 = number of sets containing zero elements , this corresponds to choosing any no element at level 0 in our recursive tree in Method 2(of combinations).
nC1 = n = number of sets containing one element , this corresponds to choosing any one element at level 1 in our recursive tree in Method 2(of combinations)
Similarly, for other binomial coefficients i.e. nC2, nC3,…………, nCn.
Total = nC0 + nC1+ nC2 +…….. = 2^n = total number of subsets in our array
Since this very condition is a proven mathematical relation. Therefore, both the methods i.e. Method 1( of including and excluding the element) and Method 2( of combinations) work correctly as they are merely the algorithmic implementations of the Right Hand Side and Left Hand Side of the above equation, respectively.
On the other hand, Method 3(of Bits Manipulation) also works perfectly fine just because of the reason that it simply iterates over all the subsets of an array (say of size n). As we all know there are 2^n possible subsets of any given set/array with n elements. As we represent each element in a subset using a bit. And we know that a bit can be necessarily either 0 or 1, therefore we can use this to denote whether the corresponding element belongs to this given subset or not. Hence, each bit pattern individually will represent a different subset of a given array.
This is the reason we frequently switch between these implementations for this problem depending on our need and all these methods work perfectly fine for us.
The End! Happy Coding!
