Roberto Jordaney, personal blog

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.

    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);
    char* strAdd(char* begin, char* end);
    void addSolution(char* solution);

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

        str1 = strAdd(result, ",1");
        str2 = strAdd(result, ",2");
        staircase(n-1, str1);
        staircase(n-2, str2);  
        free((void*)str1);
        free((void*)str2); 
    }

    char* strAdd(char* begin, char* end)
    {   
        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;
    }

    void addSolution(char* solution)
    {   
        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) 
            {
                NStepStaircase.solutions.add(result.append(",1").toString());
                return;
            }
            else if (n == 0)
            {
                solutions.add(result.toString());
                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

Python
C
Java

    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);
    char* strAdd(char* begin, int number);
    void addSolution(char* solution);

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

    char* strAdd(char* begin, int number)
    {   
        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;
    }

    void addSolution(char* solution)
    {   
        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)
            {
                solutions.add(result.toString());
                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 | \)

N Steps Staircase

My solution

Code Explanation

Generalized solution