Backtracking Flashcards
1
Q
What is backtracking?
A
It is the most direct way to write code that traverses each possible path
2
Q
When to know you reached the destination?
A
row=m, col=n, bottom right corner, and there is one additional unique path to it.
3
Q
When you should stop traversing?
A
row>m, col>n, it’s an invalid path
4
Q
row=r and col=c, what to do?
A
Two choices: Traverse to the right and traverse to the bottom.
5
Q
Total unique paths at grid (r,c) is?
A
it is equal to the sum of total unique paths from the grid to the right and the grid below
6
Q
Runtime Complexity
A
Backtracking only allows to explore possibilities, so it is the permutations of a binary string that contains m zeroes and n ones. O(m+n m)
7
Q
Space Complexity
A
O(m+n) for the recursion that goes to m+n level
