CareerCup

complexity 2^n*(logn +1). 2^n we cant avoid but can we avoid additional logn factor???

int main ()
{
	char set [] = {'a','b','c'};
	int setSize = 3; /*As per above array*/
	int totalSubset = 1<<3;
	int i,j,k;
	printf ("{{}");
	for (i = 1; i < totalSubset; i++)
	{
		printf("{");
		k=i;
		j = 0;
		while (k)
		{
			if (k&1)
			{
				printf ("%c", set[j]);
			}
			j ++;
			k = k>>1;
		}
		printf ("}");
	}
	printf ("}\n");	
}

All subsets can be easily generated by generating all the binary numbers.
initially bitArray contains all zeros.

void PrintAllSubset(int bitArray[], char set[], int length, int pos)
{
	if(pos == length)
	{
		for(int i = 0 ; i < length ; i++)
			if(bitArray[i]!=0)
				cout<<set[i]<<" ";
		cout<<endl;
		return;
	}
	for(int i = 0 ; i<= 1 ; i++)
	{
		bitArray[pos] = i;
		PrintAllSubset(bitArray, set, length, pos+1);
	}
}

This will be a JAVA alternative of Tulley. It is O(2^n) with less space complexity than simply call recursion.

/**
	 * Make super set w/o calling recursion
	 * @param array
	 */
	public static void superset(int array[]){
		int size = 1<<array.length;
		for(int i=0;i<size;i++){
			iprint(i,array);
		}
	}
	/**
	 * Print out subset with the position matching the passing parameter
	 * @param bitInt a passing parameter e.g., 6 --> 0110
	 * @param array
	 */
	private static void iprint(int bitInt, int array[]){
		int pos = array.length-1;
		System.out.print('{');
		while(bitInt > 0){
			if((bitInt & 1) == 1)
				System.out.print(array[pos]+",");
			bitInt >>= 1; pos--;
		}System.out.print('}');
	}

#include<stdio.h>
#include<conio.h>
#include<math.h>
int main()
{
int a[3]={1,2,3};
int b[3]={0,0,0};
int i,j,k;
for(i=1;i<2^3;i++)// 3 here is length of array//
{
j=i;
k=2;
printf("\n{");
while(j>0)
{
b[k]=j%2;
j=j/2;
if(b[k]==1)
{
printf("%d ",a[k]);
}
--k;
}
printf("}");
}
getchar();
getchar();
return 0;
}

Try this one its output is better than the earlier one.

#include<stdio.h>
#include<conio.h>
#include<math.h>
int main()
{
int a[3]={1,2,3};
int b[3]={0,0,0};
int i,j,k;
for(i=1;i<2^3;i++)// 3 here is length of array//
{
j=i;
k=2;
printf("\n{");
while(j>0)
{
b[k]=j%2;
j=j/2;

--k;
}
for(k=0;k<=2;k++)
{
if(b[k]==1)
printf("%d ",a[k]);}
printf("}");
}
getchar();
getchar();
return 0;
}

what if, while iterating bit pattern, we also generate the opposite one.

Example:
input: [1,2,3]

Bit Operation
000 => {}, {1,2,3}
001 => {1},{2,3}
010 => {2} , {1,3}
011 => {1,2},{3}

So, at this time, although we can stop at 2^(N-1), but for each number, we need to read the whole bit pattern of the number.

Would the time complexity is O(2^(N-1)*N) => O(2^N*N)

Just curious...

private static void subsets(int a[])
{
int pos=a.lenth.-1;
int noofsubsets=1<<a.length;
int bitmask;
System.out.println("{");
for(int i=0;i<noofsubsets;i++)
{
bitmask=i;
while(bitmask)
{
if(bitmask&1)
System.out.println(a[pos]+",");
bitmask>>1;
pos--;
}
System.out.println("}");
}
}

/**
 *
 * @author Sun
 */
public class bitmap {
    public static void main(String[] args){
        int[] test={1,2,3,4,5};
        permu(test);
    }
    public static void permu(int[] array){
        if(array==null || array.length==0)return;
        for(int i=0;i<=Math.pow(2,array.length);i++){
            System.out.println();
            for(int j=0;j<array.length;j++){
                if((i & (1<<j))>0){
                    System.out.print("  "+array[j]);
                }
            }
        }
    }
}