The Backtracking Blueprint: The Legendary 3 Keys To Backtracking Algorithms

Aug 15, 2023

The Backtracking Blueprint: The Legendary 3 Keys To Backtracking Algorithms

0/1 Code \u0026 Problem Statement @ https://backtobackswe.com/platform/co…

Free Mini DSA Course - https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions

An overview of how to solve problems using backtracking.

- We make choices, we constrain how our recursion advances and we converge toward a goal.

- It can be used in multiple problems:
N Queens
Graph coloring
Sum of Subset
0/1 Knapsack

- It is also an important concept for Artificial Intelligence.

N Queens Video: • The N Queens Problem using Backtracki…
0/1 Knapsack Video: • The 0/1 Knapsack Problem (Demystifyin…

++++++++++++++++++++++++++++++++++++++++++++++++++

Content

0.03 -> okay so to be honest I I kind of didn't have a plan for this video but I was thinking what topics

6.33 -> could we address and I mean one of my favorite topics and one topic that a lot of people have

11.37 -> questions about is the topic of backtracking and utilizing recursion to express a certain decision

18.21 -> space or express possibilities so what I really want to do with this is give you the toolkits

23.91 -> give you the blueprint that I somehow I don't know how this came to me but it just came to me from

29.67 -> doing a bunch of these problems the toolkit and and the the the patterns you can apply to these

36 -> problems and I mean it's recursion in general but specifically for backtracking problems the

41.58 -> blueprint you need to apply so what I thought up was something I always call the three keys

46.53 -> of backtracking I've done many many backtracking videos right there there there there there and

52.86 -> also here here and here so I've done a good amount of backtracking videos I mean but they're a while

58.98 -> back and I mean my video quality was pretty bad I didn't have a mic and I kind of want to re-dive

65.04 -> into this and actually explain it again so why not so what are the three keys to backtracking I

69.81 -> actually addressed this in my I think my favorite video my n Queens video which is a while back I

75.45 -> also did not have a mic the quality wasn't the best but that was one of those original videos

79.77 -> that goes a while back what I talked about is the fundamental keys to backtracking problems

85.86 -> it goes like this you make choices you have constraints on those choices and at the end

94.14 -> you're going and you're going to converge towards a goal you have a decision space you can choose

99.57 -> from your decisions are restricted somehow and your goal is is somewhere your goal is to do

106.8 -> something maybe it's to fill a string maybe it's to fill n slots maybe it's to solve a Sudoku board

112.74 -> our goal would be to solve this and what we need to do is see how each of these influence how we

118.89 -> shape our code how we shape our approach and the way we think about these problems and see how we

124.17 -> can decompose something that's intimidating like solving a Sudoku board which is the example we'll

129.24 -> do I already did a video on solving Sudoku we'll run through this as an example to demonstrate

135.07 -> these concepts that I'm trying to get across so why don't we get into it we have our choice we

141.49 -> have our constraints and we have our goal so what we need to do is we need to see what each means

145.99 -> and also as always there's a code sample in the description you can see that but I'll go through

151.81 -> the little code snippets here I'll put them right there so you can see them but yeah so let's look

157.81 -> at our first concept the choice so what I see here is I see a Sudoku board and my interviewer

164.92 -> says okay write me an algorithm that solves this I have no idea how to do this do I use two for

169.9 -> loops or something do I just go through this so what we need to fundamentally think about is the

176.83 -> core choice the core choice that we are making at each step this is how we can craft we can craft a

184.27 -> recursive function to solve a problem like this so we have a Sudoku board and yes that's a Sudoku

190.54 -> board it's a lot of stuff we we don't know how to start with this but I would say that we do know

196.09 -> how to start with it because we know the choices we're making what we need to do is we need to fill

201.61 -> these cells we need to fill those cells right and we need to fill those cells by making choices so

207.85 -> I said a key word there I said a cell so our key choice will be made on a cell so okay where does

215.29 -> a cell sit well a cell sits in a row and it sits in a column so okay I have a lead I have a lead on

223.81 -> how I can draw a function so I'll call my function solve and I'll pass in a row into column and the

230.11 -> job of the function will be to solve that specific row and column well my next question is how do I

237.01 -> solve a how do I solve a cell how do I actually do the process so let's reduce our decision space

243.76 -> we have a big Sudoku board why don't we get rid of every row except the first row so the way we need

250.78 -> to think about this is we need to think about this compartmentalizing into subproblems so are we want

257.59 -> to solve cells and when we solve all the cells in a row then we focus on the next row and the next

263.23 -> row and by the time we finish every row we will have finished but we'll get to the goal part later

268.12 -> so our choice at every single cell is going to be to place a number what are the numbers we are able

275.47 -> to choose we can choose these guys we can choose numbers from 1 through 9 so our decision space

283.54 -> that we can choose from is going to be from 1 to 9 so let's bring back that code snippet we were

289.93 -> working on that code snippet right there we're trying to solve for the row and column but what do

294.79 -> we do inside well I know I have a decision space I can place numbers 1 through 9 in the cell if it's

302.71 -> empty if it already has a number then I don't want to place a number there but if it's an empty cell

307.87 -> why don't we run a for loop so let's put a for loop right there and and there's our for loop it

313.99 -> runs from 1 to 9 I expressed my decision space we're making progress we're not lost anymore we

319.75 -> know what we're doing so far so we saw a large Sudoku board we broke the problem down into

325.72 -> solving a cell we're slowly crafting our recursive function and we're slowly getting there so what we

330.43 -> now need to think about is when I solve a cell I can place an item so once I place an item it would

337.84 -> kind of look like that so if I place an item it's going to look like that and we're going to put an

343.66 -> item in the cell and so now I've made a choice and now I need to express my constraints what

352 -> are my constraints so the thing is when we place an item I could validate the whole Sudoku board

357.61 -> but that's a waste of time that would be to the order of N squared and we don't want to do that

362.11 -> all we need to do is we need to validate the row we need to validate the column we need to validate

369.52 -> the sub grid that the number we just placed sits in so if I place a 2 here if I if in my for loop

377.89 -> my for loop says ok put a 2 there all I need to know is does the 2 break the row does it break

383.89 -> the column and does it break the sub grid so again I already have a video on the Sudoku solver stuff

390.07 -> so I don't really want to go into those logistics I really want to talk only about backtracking here

394.99 -> so ok so the key here is what we need to do is if that was a valid placement i recurse on it so why

404.98 -> don't we put our recursion right now do you see that we recurse on our decision so we recurse on

411.16 -> our decision and we'll do some exploration but do you see what I called it with why did I say

416.8 -> column plus one well I mean think about it if we solve this column what's the next logical step

422.8 -> we solve the next column and then the next so my function is a policy my function is a policy

430.84 -> that is going to know what to do based on the state that it gets input so imagine this if I

439.75 -> am at the end of this row right over here if you pass me a column that is out of bounds and

445.36 -> I am not at the final row what is the natural decision of the recursion well the recursion is

452.26 -> gonna say well just solve this cell over here go to the next row start in the first column so that

458.95 -> crafts a base case so this gets me to our goal so our goal here is to reach our base cases so

467.8 -> one base case is where we finished our row and we over bound we out of index on the row and we need

475.63 -> to go to the next row that's one base case and the final base case is when we're down here the

481.69 -> final base case is when I out of bounds on the final row when I go out of bounds on the final

487.9 -> row that means every row is finished if I go out of bounds here then that means there's more rows

494.23 -> to finish it's an outer final row but if it's our final row and we just finished it that means we've

500.08 -> finished and that craft's our base case so let's move all our decision space stuff down a little

505.54 -> and let's put our base cases right there so what we need to see here is we're slowly understanding

511.24 -> sub-problem down craft my decision space adhere to my constraints converge to a base case and now

520.45 -> what we need to do is we need to keep in mind what if the decision doesn't work out so if a

525.49 -> decision does not work out once we come back from our exploration we need to eject our decision and

532.63 -> we can put that right there and it's right there that's how we remove our decision we just remove

538.18 -> it from the cell we placed on so this is how it works we craft our function based on our choice we

544.06 -> have base cases we converge to we have a decision space and we undo our decisions after we explore

551.44 -> on them and what we do is at each of these calls each of these calls has a goal and it tells us

558.19 -> was the Sudokus solvable given the placements that we just did so these are the keys to backtracking

566.2 -> the choice you make what is the fundamental sub-problem what is the core core core decision

572.86 -> space this is our decision space for a cell our fundamental choice is choosing from this decision

579.31 -> space what we want to express in the cell once we express that we recurse on that decision if

586.87 -> the decision doesn't work we come back and we undo it and we make another choice we explore

593.41 -> we undo we make another choice so bring the code back right there that's what our for loop is for

599.68 -> our for loop is for exploration within the stack frame this cell needs to explore one through nine

606.4 -> this cell explores one through nine this or cell explores nothing it already has a number this cell

611.77 -> explores one through nine so this is one approach to solving the Sudoku problem I don't know if

616.45 -> there's a way faster than this because this is pretty exponential in time but anyway this is

623.02 -> how backtracking works this is how it pans out in my mind we make a choice we adhere to constraints

630.22 -> and we have a goal so again I've done many many videos on this channel super cool effects going

638.53 -> on right there I've done many videos on this but they were a while back and I wanted to kind of

643.51 -> retouch on this topic and give a kind of brief over look into how backtracking works and a lot

651.85 -> of times I get questions like how do you know when you have a backtracking problem so you'll know you

658.24 -> have a backtracking problem when it's easy to it's easy to express the answer recursively and that's

665.29 -> kind of hard to notice unless you have experience using backtracking often but you'll just know like

671.05 -> if it's if it says generate all if it says compute all if it says if it says generate or compute or I

678.82 -> can't really think of other words but if it says words that are exhaustive they're words implying

685 -> exhaustion of a decision space then you have a really good chance that backtracking is going to

691.72 -> be one of your solutions the only problem with backtracking for exhausting decision spaces is

696.7 -> often they are exponential in time and there may be a more there may be a smarter way to go about

702.79 -> things but this is what backtracking is about we reduced to our fundamental subproblem here and

708.7 -> yeah that's how the Sudoku solver works and again I already have a video on that I don't think the

714.28 -> video is that good like a lot of my old videos but yeah this is this is how backtracking works this

719.74 -> is the fundamental gist behind it and i really didn't have a script for this i kind of just

725.26 -> went with it and just talked a lot so that is all for this video this was a kind of briefer one and

731.44 -> less in depth into an actual question because I didn't really have notes for today but yeah this

736.99 -> is backtracking and if you ever get a question like this I mean practice helps but really

741.85 -> knowing what's going on and being comfortable with recursion really helps make these decisions and

748.18 -> making crafting these recursive functions easier it's very difficult and I honestly I'm not the

753.22 -> best at it either I still get stumped on very simple problems but the more you do it becomes

759.1 -> more straightforward and comfortable so that's all for this video if you liked this video hit the

764.89 -> like button subscribe to this channel my goal is to make this one of the world's largest resources

770.47 -> for software engineering interviews and until that happens I don't think I'm going to stop because I

775.84 -> think it's a necessity I think there just needs to be people aggressively tackling these these

782.2 -> just this space of issues and I mean this this interviewing system is kind of weird especially

789.22 -> in software engineering because a lot of people have complaints about it but I mean if we don't

793.57 -> tackle it head-on I mean nothing's going to get better if we just complain about it yeah yeah yeah

Source: https://www.youtube.com/watch?v=Zq4upTEaQyM