What is most efficient method to find all posible sub array in a given array?

Also mention its time complexity. It would be very helpful if you could also post code snippet.

Here is a link to a solution which uses bit-masking. Another approach would be to simply replicate the existing partial solution and appending the new element to the newly replicated half.

Eg: If the array is {1,2,3} and we have the solution for {1,2} as {},{1},{2},{1,2} then replicate these 4 arrays and simply append 3 to them ; ie {3},{1,3},{2,3},{1,2,3} . So this (along with the previous solution for {1,2}) is the entire solution --> {},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3}.

Note:-memcpy() can be used for array replication.

2 Likes

any code snippet for the second method would be very helpful

I am sorry it’s being difficult to put the code online. Will find a workaround though.

for(i=0;i<4;i++) {
memcpy(b[pw(i)],b[0],sizeof(b[0])*pw(i));
for(j=pw(i);j<pw(i+1);j++) {
while(b[j][k]!=0) {
k++;
}
b[j][k]=a[i];
}
}

The above code is for an array of 4 elements. Since the powerset size of 4 will be 16 , the solution array b is int b[16][4].pw() is a function that takes an int n and returns 2^n.a[] is the array having the 4 elements.
Note:-I wrote a clumsy solution. A better way would be to use vectors in c++ instead of arrays. That way u can avoid the while loop needed to append to the end of the array . Simple push_back() can be used. That would further reduce the complexity.

Thanks a lot @rohan123

The solution put by @rohan123 is of finding sub sequences in a given array. Because {1, 3} is not a sub array of the given array. It is a subsequence of the given array.

There is a difference between sub array and sub sequence.

Consider an array:

 {1,2,3,4}

Subarray: contiguous sequence in an array i.e.

{1,2},{1,2,3}

Subsequence: Need not to be contiguous, but maintains relative order i.e.

{1,2,4}

There is no meaning to comment on this thread after 6 years.

At least it will help who will query the same thing like me but won’t distract by seeing the possible solutions.

1 Like