About backtracking

#1

in the code we took this matrix,
“0000”,
“00x0”,
“000x”,
“0x00”

First we go right , we reach end of the row ,
rightSuccess=false ans we assign 1 in those positions,

now we check down side
now we are checking maze[1][3], returns true,

we go one more step down maze[2][3], there is a blockage
downSuccess=false,

1st question : am i right till now ?
2nd question : when we are getting false from both the sides, where our cursor will go, will it go back to (0,0) ?

3rd question: if it goes just one step back and check again, then which line in the code insures that ?

#2

hello @premang
answer 1-> correct
answer 2-> no it will not go back to (0,0) ,it will go one step back ( i.e it will go to the position from where it came to current position)

answer3-> no specific line . it is magic of recursion/backtracking. in recusion when we make function call then currently executing function stops and execution of new function starts . when the execution of new function is done , the control is returned to calling function and then it starts executing again. this way recusion is able to maintain previous states.

#3

i can not trace my code on stack most of the times for complex problems, but i can code it(most of the times). Does it happens to everyone ?

i check for <0, =0, steps which repeats and then i write code for dp. is this right approach ?

#4

yeah even i found it tough to dry run recursive function because of so many function calls.
one small thing i do to ensure its correctnes is to make sure that all base case are included and correct.
and the step that merge the result of small subproblem with current problem is correct.

#5

i have some more questions,
input

“0000”,
“00x0”,
“000x”,
“0x00”

step1: we go right and then down make cells value 1;
“1111”,
“00x1”,
“000x”,
“0x00”

step2: we found false, now we are returning and making cells value 0 again.
but when we reach maze[0][3] we make sol[0][3] to zero.
now we go to one step back again to maze[0][2].
1st question: will it check again that can we go right or down ?
2nd question: if yes then we made sol[0][3]=0 and from maze[0][2] we can go back to maze[0][3] position why it will not go back there ?
3rd question: if its not the case then, how it will stop at this, maze[0][1] position and checking down not ahead ?
"1100”,
“00x0”,
“000x”,
“0x00”

#6

no it will not check right (but check for down). because next satement we have writtent after right is down and because line that is calling to its right is already executed ,it will not execute again. next line will execute which call to its down.

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.