 # How to Find Subset of an array

How to Find Subset of an array
Can anyone help me with find subset of array

1 Like

in python you can simply use itertools for this…

``````import itertools

a = [1,2,3,1]
for j in range(1,len(a)+1):
for i in itertools.combinations([1,2,3,1],j):
print i
``````

Or else you can also write recursive function for same… like this…

``````a = [1,2,3,1]
l = len(a)
current = []
def find(index):
global current
if index == l:
return
else:
find(index+1)
current.append(a[index])
print current
find(index+1)
current.pop()
print find(0)``````

Hey @drjaat,

There are quite a few ways to generate subsets of an array,

• Using binary representation, in simple terms if there are 3 elements in an array,

A = [1,2,3]

subsets of array will be {[],1,,,[1,2],[2,3],[1,3],[1,2,3]}

How to generate?

• n elements in an array than it’s for sure that there would be 2^n subsets of that array.
• for three elements, find all the possible binary representation of n bits in size
• let’s suppose for three elements 000, 001, 010, 011, 100, 101, 110, 111
• wherever there is 1 select those elements for set, 000 no elements are chosen, for 001 only 3 is chosen and so on. {[],,,[2,3],1,[1,3],[1,2],[1,2,3]}

Implementation part would be now easy, you can read go through this link for better explanation.

Hope this helps!

1 Like

You can use the below snippet to find all subsets of a given array of size n.

int n,a[n];

void foo(int count,vector < int > vec)

{

if(count==n)

{

print(vec);return;

}

foo(count+1,vec);

vec.push_back(vec[count]);

foo(count+1,vec);

}

4 Likes

Here is a link where you can find the code for finding all possible subsets of a given set http://www.geeksforgeeks.org/finding-all-subsets-of-a-given-set-in-java/

The above code is in Java if you want a c++ code you can find it here http://www.geeksforgeeks.org/power-set/

I Hope it helps.

2 Likes

import java.io.IOException;
class Main
{
static void printSubsets(char set[])
{
int n = set.length;

``````    // Run a loop for printing all 2^n
// subsets one by obe
for (int i = 0; i < Math.pow(2,n); i++)
{
for (int j = 0; j <Math.pow(2,n); j++){
if((i & (1<<j)) > 0 ){
//System.out.print("("+i+" "+j+")"+" ");
System.out.print(set[j]+" ");
}
}
System.out.println();
}
}
// Driver code
public static void main(String[] args)
{
char set[] = {'a', 'b', 'c'};
printSubsets(set);
}
``````

}

i dont want to print non continous for example a is 1 and c is 3 so i dont want to print it
i only want to print continous set eg a,b,ab,abc,c,bc

@drjaat and others…Can this logic be used for finding subset of an array with n elements?
If so. How?

(because for 5 elements we need to generate 00000,00001,00010,00011…11111. )
I would like to print both contiguous & non-contigious.

One can start with 00000.Use shift operator. But I cannot apply this operator correctly to get the exact sequence of
00000,00001…11111.

can any one help

import java.util.ArrayList;
public class place2 {
public static void main(String[] args) {
int a[]= {1,2,3,4};
ArrayList ans=new ArrayList();
for(int k=1;k<=a.length;k++){
for(int i=0;i<=a.length-k;i++){
String s="";
for(int j=i;j<i+k;j++)
s+=a[j];
if(s!="")