Advanced Recursion Problems | C++ Placement
Recursion - II
Permutation
To print all the permutations of a string.
Idea: for each character s[i] in the given string, we add a character in the ans string and then solve solve s.substr(0,i) + s.substr(i+1)
Sample Input:
ABC
Sample Output:
ABC
ACB
BAC
BCA
CAB
CBA
Time Complexity: O(N*2n )
Space Complexity: O(2n )
permutation(s, “”) will give the required answer
CountPaths
Find the number of ways to reach e from s. Idea:
We have 6 ways to go forward (1,2,3,4,5,6).
At the starting point s,
Current answer = countPath(s+1,e) + countPath(s+2,e) + countPath(s+3,e) + countPath(s+4,e) + countPath(s+5,e) + countPath(s+6,e)
Time Complexity: O(2n)
Space Complexity: O(2n)
CountPathMaze
Given a 2D grid, find the number of ways to reach (n-1, n-1).
You can go to (i,j) from (i-1,j) and (i,j-1).
Time Complexity: O(2n)
Space Complexity: O(2n)
Comments
Post a Comment