Backtracking was HARD until I learned it this way | Backtracking tutorial

Añadido: 2026-05-24

[00:00:00]Backtracking. If you've been preparing for coding interviews, you've probably heard this word and felt your stomach drop a little.

[00:00:07]It has a reputation. People see backtracking problems in interviews and go completely blank.

[00:00:14]Not because they're not smart enough, but because nobody ever explained the actual intuition behind it.

[00:00:20]Here's what I want you to take away from this video.

[00:00:23]Backtracking is not a new algorithm.

[00:00:25]It's not magic. And by the end of this, you won't just know what it is, you'll have the core intuition to look at any backtracking problem [music] and know exactly where to start.

[00:00:36]Let's start with a problem. Given a number n, generate all strings of length n using only the letters A and B.

[00:00:44]Your first instinct, nested loops. One loop per character. Makes sense for n equals 2, but what if n is 10?

[00:00:52]You'd have to write 10 nested loops.

[00:00:55]That's not a program, that's a cry for help.

[00:00:58]You can't hardcode a different program for every n.

[00:01:01]There has to be a better way.

[00:01:03]And there is.

[00:01:04]Let's simplify.

[00:01:05]n equals 2.

[00:01:07]Generate all strings of length 2 using A and B.

[00:01:11]Start with an empty string.

[00:01:12]For the first character, two choices.

[00:01:15]Add A or add B.

[00:01:17]From A, same thing. Add A [music] or add B.

[00:01:21]From B, same. Add A or add B.

[00:01:25]Look at what just happened. You built a tree.

[00:01:28]And the answers?

[00:01:29]AA, AB, BA, BB.

[00:01:34]They're just the leaf nodes of that tree.

[00:01:37]So, instead of asking, "How do I generate all strings?" ask a completely different question.

[00:01:42]"How do I traverse this tree?"

[00:01:45]And that answer is simple. DFS.

[00:01:49]That is the entire idea behind backtracking. You are doing DFS on a tree you build as you go.

[00:01:56]Now, here's what makes backtracking feel different from regular DFS.

[00:02:00]In a normal DFS problem, the tree is given to you. It's already there. You just traverse it.

[00:02:10]In backtracking, the tree is invisible.

[00:02:12]It doesn't exist yet. You build it as you go. At every step, you ask, "What choices can I make right now?"

[00:02:19]Those choices become the branches. You go deeper. You hit a leaf. You come back.

[00:02:25]You try the next branch.

[00:02:26]That going back, that's the backtracking part. But, how exactly does the code go back?

[00:02:32]This is the question most explanations skip.

[00:02:35]Let's not skip it. Here's what's actually happening when the code backtracks.

[00:02:39]Say we're building our string and we've added A, then A again. Path is AA.

[00:02:45]That's a valid answer. We record it.

[00:02:47]Now, we need to try AB.

[00:02:49]But, the path still has AA in it. How do we get from AA to AB?

[00:02:54]We remove the last character. Pop the A off the end. Path goes back to just A.

[00:03:00]Now, we add B.

[00:03:01]Path becomes AB. New answer.

[00:03:04]And when we've explored everything starting with A, we pop that, too.

[00:03:08]Path goes back to empty. Then, we try B.

[00:03:13]That pop, that single operation, is what makes the whole thing work. Without it, you'd keep going forward forever. You'd never explore a different branch. The entire tree would be invisible and unreachable.

[00:03:26]Path.pop is not cleanup. It's the mechanism. It's what puts you back at the previous state, so you can try something different. Now, the code will make complete sense.

[00:03:36]Before writing anything, answer two questions. Question one, "When do I have a complete answer?

[00:03:42]When do I stop going deeper and record what I have?"

[00:03:45]Question two, "What choices can I make from here?

[00:03:49]What are the branches I can take from the current state. For our AB problem, question one, path has length n. That's a complete answer. Record it. Question two, at every step, add A or add B.

[00:04:05]Three parts to the code, check if done, loop through choices, pop after each one. That pop at the end of the loop, that's the backtracking. It runs after every single recursive call, putting you back exactly where you were before that choice was made. Let's watch it run for n equals two.

[00:04:23]Empty path, choose A. Path is A. Not done, go deeper. Choose A again. Path is AA.

[00:04:32]Length two, record AA. Pop. Path is back to A. Choose B.

[00:04:38]Path is AB. Length two, record AB. Pop.

[00:04:43]Path is A.

[00:04:45]No more choices from A.

[00:04:47]Pop. Path is empty. Choose B. Path is B.

[00:04:51]Go deeper. Choose A. Path is BA. Record BA. Pop. Path is B. Choose B. Path is BB.

[00:05:01]Record BB.

[00:05:03]Pop. No more choices from B.

[00:05:06]Pop. Path is empty again.

[00:05:09]And with this, we are done with the whole program. Every pop put us back exactly one step. That's all backtracking is.

[00:05:17]Backtracking is DFS on a tree you build as you go.

[00:05:21]Every node is a partial state. Every branch is a choice. Every leaf is a complete answer. When you see generate all, find all combinations, return all possible, draw the tree. Answer two questions. When do I have a complete answer? What choices can I make from here? Write the loop, add the pop. Done.

[00:05:39]AlgoMonster has every pattern covered with interactive visualizers, where you can watch the tree build in real time.

[00:05:46]Link in the description. See you in the next one.