## Expedia Interview Question

Software Engineer / DevelopersAssumptions: Input is String instead of char array.

Code is in Java:

```
public static void printAllSubsets(String s){
int[] base=new int[s.length()];
String s1="";
while(!s1.equals(s)){
s1="";
nextCombination(base);
for(int i=0;i<base.length;i++){
if(base[i]==1){
s1=s1+s.charAt(i);
}
}
System.out.println(s1);
}
}
public static void nextCombination(int[] arr){
int i=arr.length-1;
while(i>=0){
if(arr[i]==0){
break;
}
i--;
}
if(i<0){
return;
}
arr[i++]=1;
while(i<arr.length){
arr[i++]=0;
}
}
```

I think one approach that may work is dynamic programming. If you do it bottom-up, you can find all combinations. However, if I'm not mistaken, DP is usually O(n^2) or worse, and doing it iteratively is a downhill compilation task.

You can represent each combination as a binary number with n bits. If the bit is on, the letter in that index is included in the combination. For a string of length n there are 2^(n+1)-1 combinations (if you include the empty set as a subset), therefore I don't think you can do it in less than 2^(n+1) time. I think that's the idea behind kg's response.

Ouput: x1...xn where xi denotes whether the i-th element of the input appears in the subset or not

```
#include <stdio.h>
#include <stdlib.h>
void gen(int* input, int n, int index);
int main(int argc, char* argv[])
{
int *input;
int n;
if (argc != 2) {
printf("Usage: %s <#elements>\n",argv[0]);
exit(0);
}
n = atoi(argv[1]);
input = malloc(sizeof(int)*n);
gen(input,n,0);
}
void gen(int* input, int n, int index)
{
int i;
if (index == n) {
for (i = 0; i < n; i++)
printf("%d",input[i]);
printf("\n");
return;
}
input[index] = 0;
gen(input,n,index+1);
input[index] = 1;
gen(input,n,index+1);
}
```

Yet another solution,

public static void combination(Queue<String> input,List<String> result ) {

if (input.Count == 0) return;

string seed = input.Dequeue();

List<String> copy = new List<string>(result);

foreach (String o in copy) {

result.Add(seed + o);

}

result.Add(seed);

combination(input, result);

}

Take each character in the input character array and put it in a Queue. Pass this queue to the above method.

#include <stdio.h>

#include <math.h>

int main() {

int a[] = {1,2,3,4,5}, size;

size = sizeof(a)/sizeof(a[0]);

for (int i = 0; i < pow(2.0, size); ++i) {

printf("{");

for (int j = 0; j < size; ++j)

if (((i >> j) & 1) == 1)

printf(" %d ", a[j]);

printf("}\n");

}

return 0;

}

"Present" string as binary. If i-th bit ON print character i.

L - length of the string;

2^(L-1) - number of combinations

- zdmytriv March 11, 2008