# N Steps Staircase

The text of the exercise is the following:

There’s a staircase with N steps, and you can climb 1 or 2 steps at a time. Given N, write a function that prints all the unique ways you can climb the staircase. The order of the steps matters.

For example, if N is 4, then there are 5 unique ways:

1, 1, 1, 1
2, 1, 1
1, 2, 1
1, 1, 2
2, 2

What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time. Generalize your function to take in X.

Before solving the exercise, we can ask few questions to specify few aspects that might not be clear.

• Are the steps going to be always positive number? Yes.

• In the general case, is 1 going to be always in the possible steps? No.

### My solution

    N = 4
solutions = []

def staircase(n, result):

if n == 1:
solutions.append(result+","+"1")
return

if n == 0:
solutions.append(result)
return

staircase(n-2, result + ",2")
staircase(n-1, result + ",1")

if __name__ == "__main__":
staircase(N,"")
print("\n".join([s[1:] for s in solutions]))

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>

char** solutions;
int N = 4;
int n_solution=0;

void staircase(int n, char *result);

void staircase(int n, char *result)
{
char *str1,*str2;
if (n == 1)
{
free((void*)str1);
return;
}
else if (n == 0)
{
return;
}

staircase(n-1, str1);
staircase(n-2, str2);
free((void*)str1);
free((void*)str2);
}

{
char* str;
str = (char*) malloc(sizeof(char) * (strlen(begin)+ strlen(end) + 1));
if (str == NULL) exit(1);
str = strcpy(str, begin);
str = strcat(str, end);
return str;
}

{
char *str = (char*) malloc(sizeof(char) * strlen(solution) + 1);
if (str == NULL) exit(1);
n_solution++;
solutions = (char**) realloc(solutions, sizeof(char*) * n_solution);
if (solutions == NULL)
{
free(solutions);
exit(1);
}
str = strcpy(str, solution);
solutions[n_solution-1] = str;
return;
}

int main(int argc, char* argv[])
{
int i;
solutions = solutions=malloc(sizeof(char**));
if (solutions == NULL) exit(1);
staircase(N,"");

for(i=0; i< n_solution; i++ )
{
printf("%s\n", solutions[i]+1);
free((void*)solutions[i]);
}
free(solutions);

return 0;
}

    import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class NStepStaircase {

static List<String> solutions = new ArrayList<String>();

public static void main(String[] args)
{
int N=4;
staircase(N, new StringBuffer());
Iterator<String> iter = NStepStaircase.solutions.iterator();
String str;
while(iter.hasNext())
{
str = iter.next();
System.out.println(str.substring(1, str.length()));
}
}

static void staircase(int n, StringBuffer result)
{
if (n == 1)
{
return;
}
else if (n == 0)
{
return;
}

staircase(n-1, new StringBuffer(result).append(",1"));
staircase(n-2, new StringBuffer(result).append(",2"));
}
}


### Code Explanation

The function staircase is a recursive function that takes the n and result as input parameters.

• n represents the number of stairs that remains to be climbed.

• result represents the steps covered so far.

The recursion stops when there are no more steps to climb or when there are only 1 stair left.

Time complexity: $$O(2^N)$$

Space complexity: $$O(2^N)$$

### Generalized solution

    N = 9
solutions = []
STEPS = [1, 3, 5]

def staircase(n, result):

if n == 0:
solutions.append(result)
return

for s in STEPS:
if n-s >= 0:
staircase(n-s, result + "," + str(s))

if __name__ == "__main__":
staircase(N,"")
print("\n".join([s[1:] for s in solutions]))

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

char** solutions;
int N = 4;
int n_solution=0;
int STEPS[] = {1,2,3};

void staircase(int n, char *result);

void staircase(int n, char *result)
{
char *str;
if (n == 0)
{
return;
}
for (int i=0; i<sizeof(STEPS)/sizeof(STEPS); i++)
{
if ( n-STEPS[i] >= 0)
{
staircase(n-STEPS[i], str);
free((void*)str);
}
}
}

{
char* str;
str = (char*) malloc(sizeof(char) * (strlen(begin)+ floor(log10(number))+1 +1 + 1)); //1 for '\0', 1 for ',', 1 for
if (str == NULL) exit(1);
sprintf(str, "%s,%d", begin, number);
return str;
}

{
char *str = (char*) malloc(sizeof(char) * strlen(solution) + 1);
if (str == NULL) exit(1);
n_solution++;
solutions = (char**) realloc(solutions, sizeof(char*) * n_solution);
if (solutions == NULL)
{
free(solutions);
exit(1);
}
str = strcpy(str, solution);
solutions[n_solution-1] = str;
return;
}

int main(int argc, char* argv[])
{
int i;
solutions = solutions=malloc(sizeof(char**));
if (solutions == NULL) exit(1);
staircase(N,"");

for(i=0; i< n_solution; i++ )
{
printf("%s\n", solutions[i]+1);
free((void*)solutions[i]);
}
free(solutions);

return 0;
}

    import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Arrays;

public class NStepStaircaseGeneral {

static List<String>  solutions = new ArrayList<String> ();
static List<Integer> STEPS     = new ArrayList<Integer>(Arrays.asList(1,2));

public static void main(String[] args)
{
int N=4;
staircase(N, new StringBuffer());
Iterator<String> iter = NStepStaircaseGeneral.solutions.iterator();
String str;
while(iter.hasNext())
{
str = iter.next();
System.out.println(str.substring(1, str.length()));
}
}

static void staircase(int n, StringBuffer result)
{
Iterator<Integer> iter = NStepStaircaseGeneral.STEPS.iterator();
Integer step;
if (n == 0)
{
return;
}
while (iter.hasNext())
{
step = iter.next();
if ((n - step) >= 0)
{
staircase(n-step, new StringBuffer(result).append(","+step));
}
}
}
}


Time complexity: $$O(k^N)$$ $$;$$ $$k = | STEPS |$$

Space complexity: $$O(k^N)$$ $$;$$ $$k = | STEPS |$$