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);
    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

    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 | \)