00:00Hi everyone, today we are going to talk about the topic in which we are going to study the lecture,
00:03its name is backtracking
00:05Now, we have seen many different concepts in recursion
00:09The first one was basics of recursion
00:11Then we studied divide and conquer, which we discussed merge, sort and quicksort
00:17And today we are going to talk about recursion-based concepts, which we call backtracking
00:22In English, it means that we are going to go on a path and we are going to go on
00:27a path
00:29So, when we follow the same path, we are going to go backtracking
00:36So, when we start recursion, we call backtracking concept in Java
00:43Now, many of us have seen the maze, but we have not seen in real life
00:46So, this photo is a maze, maze, or a maze
00:50So, it is a maze inside, we have an entry point, we are going to go there
00:56Then, we try to find the right path or exit
01:00And, as we go to a point, where we know that there is no right path exists
01:06So, what do we do here? We start to move here
01:09We move and we try to re-trace our steps
01:11And, in the same way, we try to find the right path
01:15And, in this way, we can find the right path again
01:19So, we start to backtrack there again
01:23So, this concept, where we have an entry point, a starting point
01:28And, what do we do here? We have to find solutions for some problem
01:32So, what do we do here? We try to go in every possible direction
01:36And, see if there is a solution in this direction
01:38Or, if there is a solution in this direction
01:41And, if we realize that we are not going in the right direction
01:46Or, the choice we had first taken in recursion
01:48That was a wrong choice
01:49So, what do we do here? Backtrack
01:50So, what do we do here? Return it
01:53As we know that there is no solution here
01:56So, using this process, we are going to solve many questions
02:02Backtracking is used in many questions
02:04But, the concept of backtracking is very simple
02:07In fact, if we understand 2-3 questions, the concept of backtracking will be clear
02:12Like, if we understand N-queen, Sudoku solver
02:17We are going to do these questions in this chapter
02:19This question is going to be well
02:21This question is going to be well
02:22This question is going to be well
02:22Grid ways are going to be well
02:25Then, my backtracking concepts will be clear
02:28Backtracking is a very easy concept
02:30There is no problem
02:33There is no problem
02:33There is no code
02:35But, it is a little lengthy
02:36Like, N-queen code is a little lengthy
02:38If we don't use bit manipulation
02:41So, the code of Sudoku is a little lengthy
02:43So, it will take a little time to write code
02:46But, backtracking
02:47If divide and conquer was clear
02:49Recursion basics clear
02:50So, it will take a very easy topic
02:52It will take a very easy topic