Data Structures and Algorithms(DSA) Concept — Subsets and Subsequence .
Topics : Difference between subarrays, subsets and subsequence.DSA interview questions based on subsets and subsequence.
What is the difference between subarrays, subsets and subsequence?
Consider an array A
A = [ 3, 2, 1, 9, 6, 8 ]
Below are arrays formed from elements of A,Lets see which of these arrays are
subarrays , subset , and subsequence.
is_subarray is_subseq is_subset
[3, 2, 1] True True True
[1, 9, 6, 8] True True. True
[9] True True. True
[ 3, 2, 1, 9, 6, 8 ]. True True. True
[ 2, 9, 6 ] False True True
[ 3, 8 ] False True True
[ 2, 1, 6 ] False True True
[ 9, 1, 2] False False True
[ 3, 2, 6, 9 ] False False True
So from the example we can see that
Subarrays are contiguous part of the array.Order of the elements matter.
Subsequence are made from any element of the array as long as the order of
the element in 'A' does not change.
Subsets,any array made from elements of the array , even without considering
the order of elements in array 'A'.Note :
Number of subsequences = 2^N , where N is the number of elements in the array.
Q 1. Given an array A of size N . Check if there exists a subsequence with a sum equal to K.
Lets Try to use what be learnt in bit manipulation to solve this problem.
// Link to Bit manipulation blog can be found at the end of this blog.
first We can see that the number of subsequence is 2^N, where N is the length
of the array
consider the array
A = [ 5, 2, 6 ,8 ]
We can see that the number subsequence is 2^4 = 16
so lets try to find all the subsequence, we can use bit value representation
of number of subsequence to find the subsequence.
number Array
of 5 2 6 8 Sum of
Subsequence Subsequence
-----------------------------------------------------------------
0 bit-> 0 0 0 0 0
1 0 0 0 1 A[0]
2 0 0 1 0 A[1]
3 0 0 1 1 A[1]+A[0]
4 0 1 0 0 A[2]
5 0 1 0 1 A[2]+A[0]
.
.
.
.
.
15 1 1 1 1 A[3]+A[2]+A[1]
+A[0]
We can can see that by using the bit of number of subsequence we can
iterate through all the subsequence.
lets look at how the code will look like.
public boolean findSubseq(int[] A,int k){
int N= A.length;
for(int i=0;i<2^N;i++){
int sum=0;
for(int p=0;p<N;p++){
if((i>>p)&1==1){
sum+=A[p];
}
}
if(sum==K){
return true;
}
}
return false;
}TC : O( N x 2^N)
Q 2 . Given an array A of size N . Calculate sum of max of every subsequence.
Approach 1 :
follow the steps on the last questions to generate all the sub sequences.
Get the max of every subsequence .
Keep adding max.
TC : O(N x 2^N)
Approach 2 :
By finding out how many subsequence a element contributes to as the max element
for every A[i] calculate the number of smaller , lets say it is 'c' .
count of subsequences where A[i] is the max is 2^c.
we can calculate the number of elements smaller than A[i] by simply sorting the
array A.
Eg:
A= [ 4, 7, 2, 5, 8, 10 ]
after sorting.
2 4 5 7 8 10
element<A[i] 0 1 2 3 4 5
# of subseq
where A[i] is 2^0 2^1 2^2 2^3 2^4 2^5
max
--------------------------------------------------------------
sum of max = 2 + 8 + 20 + 56 + 128 + 320
lets see this in code .public long SumOfMax(int[] A){
long ans =0;
Arrays.sort(A);
for (int i=0;i<n; i++){
long contribution = A[i]x(1<<i);
ans+=contribution
}
return ans;
}Hope this was helpful , please do like and follow.
Up next :
Reference:
