I saw this interview question on a LinkedIn group here
To summarise, if I have an array
[1,2,3,4,5]
and input
3
I require the output
[1,2,3], [3,2,1], [2,3,1], [2,1,3], [1,3,2], [3,1,2], [2,3,4], [4,3,2],...
In no particular order.
I have been thinking about this one for a while now. I have come up with various different ways of solving but all methods use for-loops.
I think it's clear that in order to eliminate loops it must be recursive.
I thought I got close to doing this recursively partitioning the array and joining elements, but with great frustration I ended up requiring another for loop.
Im beginning to think this is impossible (which it can't be, otherwise why the interview question?).
Any ideas or links? The amount of possible outputs should be 5PN, where N is the input.
The following recursive algorithm will attempt to print every subset of {1,.., n}. These subsets are in one to one with numbers between 0 and 2^n-1 via the following bijection: to an integer x between 0 and 2^n-1, associate the set that contains 1 if the first bit of x is set to one, 2 if the second bit of x is set to one, ..
void print_all_subsets (int n, int m, int x) {
if (x==pow(2,n)) {
return;
}
else if (x has m bits set to one) {
print the set corresponding to x;
}
print_all_subsets(n,m,x+1);
}
You need to call it with n = 5 (in your case), m=3 (in your case), and x = 0.
Then you need to implement the two functions "print the set corresponding to x" and "x has m bits set to one" without for loops... but this is easily done using again recursion.
However, I think this is more of a challenge -- there is no point in completely eliminating for-loops, what makes sense is just to use them in a smart way.