- Blogathon, Blogathon-2021, Recursion, Strings

Print all ways to reach the Nth stair with the jump of 1 or 2 units at a time

Given a positive integer N representing N stairs and a person it at the first stair, the task is to print all ways to reach the Nth stair with the jump of 1 or 2 units at a time.Examples:Input: N = 3Output: 112Explanation:Nth stairs can be reached in the following ways with the jumps of 1 or 2 units each as:Perform the two jumps of 1 unit each as 1 -> 1.Perform the two jumps of 1 unit each as 2.Input: N = 5Output:111111212121122Approach: The given problem can be solved using Recursion. The idea is to cover both the cases of one or two jumps at a time at each index and print all the possible ways to reach the Nth stair. Follow the steps below to solve the given problem:Define a recursive function, say totalPossibleJumps(int N) that returns all possible ways of jumps to reach the Nth stair.At the starting point of recursion check for the base cases as:If the N < 0, then it is not a valid way. So return an empty arrayIf the N = 0, then it is a valid way. So return an array of size 1 containing an empty space.Call recursive function two times at each recursion call one for 1 unit jump and another for the 2 unit jump and store results separately.Initialize an array of strings, say totalJumps to store ways to reach the ith index and store all possible ways of reaching the index i with the results stored in the above two recursive calls.After completing the above steps, print all the possible combinations return by the above recursive calls as totalPossibleJumps(N).Below is the implementation of the above approach: C++#include using namespace std;vector TotalPossibleJumps(int N){        if ((N - 1) == 0) {        vector newvec;        newvec.push_back("");        return newvec;    }    else {        if (N < 0) {            vector newvec;            return newvec;        }    }        vector jump1        = TotalPossibleJumps(N - 1);    vector jump2        = TotalPossibleJumps(N - 2);        vector totaljumps;            for (string s : jump1) {        totaljumps.push_back("1" + s);    }            for (string s : jump2) {        totaljumps.push_back("2" + s);    }    return totaljumps;}int main(){    int N = 3;    vector Ans = TotalPossibleJumps(N);    for (auto& it : Ans)        cout