There are n rocks in the river, using which the frog can leap across the river.

I saw a discussion on this question on careercup as its good question..so i pasted it here

A frog has to cross a river. There are n rocks in the river, using which the frog can leap across the river. On its way across the river the frog can chose to skip a rock, but it cannot skip two consecutive rocks because that would be two far a distance for the frog to hop, also the from would not skip the first rock and the last rock. E.g. if there are 3 rocks, 1,2,3 and 4, there could be three following routes it could take:
1,2,3,4
1,2,3,4
1,3,4
1,2,4

Write a recursive algorithm, that takes a number of rocks' and prints all the feasible paths. Ofcourse there can be other arguments too.



A frog has to cross a river. There are n rocks in the river, using which the frog can leap across the river. On its way across the river the frog can chose to skip a rock, but it cannot skip two consecutive rocks because that would be two far a distance for the frog to hop, also the from would not skip the first rock and the last rock. E.g. if there are 3 rocks, 1,2,3 and 4, there could be three following routes it could take:
1,2,3,4
1,2,3,4
1,3,4
1,2,4

Write a recursive algorithm, that takes a number of rocks' and prints all the feasible paths.


#include
#include
#include


void printFrogLeap (int* pArray, int num, int count)
{
if(count > num)
{
return;
}
if(count == num)
{
int i;
if(pArray[count-1] == 1) /*path is complete or not*/
{
for (i=0; i < num; i++)
{
if (pArray[i] == 1)
{
printf ("[%d]", i+1);
}
}
printf ("\n");
}
return;
}
pArray [count] = 1;
printFrogLeap (pArray, num, count+1);
if(count+1 < num)
{
pArray [count+1] = 0;/*exclude this entry from path, since its used*/
}
printFrogLeap (pArray, num, count+2);
if(count+2 < num)
{
pArray [count+2] = 0;/*exclude this entry from path, since its used*/
}
}



int main ()
{
int *array, num=4;

array = (int*)malloc (sizeof(int)*num);
memset (array,0x00,num);
printf ("Total paths: \n");
printFrogLeap (array, num, 0);
free (array);
return 0;
}

Run Here https://ideone.com/o00za
Solution By Tully From CareerCup