## nitish712

BAN USER
Employee at None

Questions (2)

Comments (5)

Reputation 10

Page:

1

Comment hidden because of low score. Click to expand.

Comment hidden because of low score. Click to expand.

0

of 0 vote

@ashish In order to improve it, i guess we need to find a faster way of finding the positions of set bits...it is as follows:

For each number 'p' that we convert into binary .. do as follows:

```
int itr2=0;
while(p>0)
{
int tmp=p;
p = p&(p-1);
tmp-=p;
int pos = log2(tmp);
subset[itr2++]=str[pos];
}
subset[itr2]='\0';
```

The time complexity now will be:

total number of set bits from 0 to 2^n-1 = n*2^(n-1) = O(n*2^n).

But the advantage is that running time is reduced to nearly half of the previous algorithm.

I guess this can't still be reduced.. :) :)

Comment hidden because of low score. Click to expand.

Comment hidden because of low score. Click to expand.

0

of 0 vote

```
#include <stdio.h>
#include <string.h>
int main()
{
//assuming the string has distinct characters... (or else one can also pick out the distinct chars ..)
char str[20];
strcpy(str, "abcdef");
int len = strlen(str);
int start_val=(1<<len)-1;
char subset[20];
int itr1, itr2;
while(start_val >=0)
{
int tmp=start_val;
itr1=itr2=0;
while(itr2!=len)
{
if(tmp&1)
subset[itr1++] = str[itr2];
tmp >>=1;
itr2++;
}
subset[itr1]='\0';
printf("%s\n", subset);
start_val--;
}
return 0;
}
```

This code will print all possible subsets of the given string.

- nitish712 June 03, 2013Comment hidden because of low score. Click to expand.

Page:

1

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

@amnesiac.. the inner loop is for selecting which letters are to be kept in the current subset. This is decided by checking the set bits of the current number('tmp' in this case). :) :)

- nitish712 June 04, 2013