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 = 3
Output:
11
2
Explanation:
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 = 5
Output:
1111
112
121
211
22
Approach: 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 array
- If 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.
- At the starting point of recursion check for the base cases as:
- 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++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find all the ways to reach// Nth stair using one or two jumpsvector<string> TotalPossibleJumps(int N){ // Base Cases if ((N - 1) == 0) { vector<string> newvec; newvec.push_back(""); return newvec; } else { if (N < 0) { vector<string> newvec; return newvec; } } // Recur for jump1 and jump2 vector<string> jump1 = TotalPossibleJumps(N - 1); vector<string> jump2 = TotalPossibleJumps(N - 2); // Stores the total possible jumps vector<string> totaljumps; // Add "1" with every element // present in jump1 for (string s : jump1) { totaljumps.push_back("1" + s); } // Add "2" with every element // present in jump2 for (string s : jump2) { totaljumps.push_back("2" + s); } return totaljumps;}// Driver Codeint main(){ int N = 3; vector<string> Ans = TotalPossibleJumps(N); for (auto& it : Ans) cout << it << '\n'; return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to find all the ways to reach // Nth stair using one or two jumps static ArrayList<String> TotalPossibleJumps(int N) { // Base Cases if ((N - 1) == 0) { ArrayList<String> newvec = new ArrayList<String>(); newvec.add(""); return newvec; } else { if (N < 0) { ArrayList<String> newvec = new ArrayList<String>(); return newvec; } } // Recur for jump1 and jump2 ArrayList<String> jump1 = TotalPossibleJumps(N - 1); ArrayList<String> jump2 = TotalPossibleJumps(N - 2); // Stores the total possible jumps ArrayList<String> totaljumps = new ArrayList<String>(); // Add "1" with every element // present in jump1 for (String s : jump1) { totaljumps.add("1" + s); } // Add "2" with every element // present in jump2 for (String s : jump2) { totaljumps.add("2" + s); } return totaljumps; } // Driver Code public static void main(String[] args) { int N = 3; ArrayList<String> Ans = TotalPossibleJumps(N); for (String it : Ans) System.out.println(it); }}// This code is contributed by ukasp. |
Python3
# python program for the above approach# Function to find all the ways to reach# Nth stair using one or two jumpsdef TotalPossibleJumps(N): # Base Cases if ((N - 1) == 0): newvec = [] newvec.append("") return newvec else: if (N < 0): newvec = [] return newvec # Recur for jump1 and jump2 jump1 = TotalPossibleJumps(N - 1) jump2 = TotalPossibleJumps(N - 2) # Stores the total possible jumps totaljumps = [] # Add "1" with every element # present in jump1 for s in jump1: totaljumps.append("1" + s) # Add "2" with every element # present in jump2 for s in jump2: totaljumps.append("2" + s) return totaljumps# Driver Codeif __name__ == "__main__": N = 3 Ans = TotalPossibleJumps(N) for it in Ans: print(it) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to find all the ways to reach// Nth stair using one or two jumpsstatic List<string> TotalPossibleJumps(int N){ // Base Cases if ((N - 1) == 0) { List<string> newvec = new List<string>(); newvec.Add(""); return newvec; } else { if (N < 0) { List<string> newvec = new List<string>(); return newvec; } } // Recur for jump1 and jump2 List<string> jump1 = TotalPossibleJumps(N - 1); List<string> jump2 = TotalPossibleJumps(N - 2); // Stores the total possible jumps List<string> totaljumps = new List<string>(); // Add "1" with every element // present in jump1 foreach (string s in jump1) { totaljumps.Add("1" + s); } // Add "2" with every element // present in jump2 foreach (string s in jump2) { totaljumps.Add("2" + s); } return totaljumps;}// Driver Codepublic static void Main(){ int N = 3; List<string> Ans = TotalPossibleJumps(N); foreach(string it in Ans) Console.WriteLine(it);}}// This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script> // JavaScript program for the above approach // Function to find all the ways to reach // Nth stair using one or two jumps const TotalPossibleJumps = (N) => { // Base Cases if ((N - 1) == 0) { let newvec = []; newvec.push(""); return newvec; } else { if (N < 0) { let newvec = []; return newvec; } } // Recur for jump1 and jump2 let jump1 = TotalPossibleJumps(N - 1); let jump2 = TotalPossibleJumps(N - 2); // Stores the total possible jumps let totaljumps = []; // Add "1" with every element // present in jump1 for (let s in jump1) { totaljumps.push("1" + jump1[s]); } // Add "2" with every element // present in jump2 for (let s in jump2) { totaljumps.push("2" + jump2[s]); } return totaljumps; } // Driver Code let N = 3; let Ans = TotalPossibleJumps(N); for (let it in Ans) document.write(`${Ans[it]}<br/>`);// This code is contributed by rakeshsahni</script> |
Output:
11 2
Time Complexity: O(2N )
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
