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

general
, , ,
1

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

2

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.

1 Like
3

any code snippet for the second method would be very helpful

4

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];
}
}

5

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.

6

Thanks a lot @rohan123