Videos / DSA

Episode 12 of 22 · DSA, end to end

Recursion and backtracking: trusting the smaller problem

Chapters

1. Ask the queue0:00
2. The two clauses0:17
3. The leap of faith0:35
4. What a frame is0:54
5. Down, then back up1:11
6. The descent that never ends1:25
7. Draw the tree1:41
8. Fifteen calls1:59
9. Branching factor and depth2:15
10. The table that collapses it2:34
11. How the problem shrinks2:53
12. Nodes cost time, depth costs space3:09
13. The mark you rub out3:24
14. Push, recurse, pop3:41
15. Undo everything you did3:58
16. The one missing undo4:14
17. Copy it, or restore it4:29
18. A tree you never build4:46
19. One stencil5:03
20. Take it or skip it5:22
21. The branching shrinks5:39
22. Never look backwards5:56
23. A column and two diagonals6:16
24. Four problems, three slots6:34
25. The closed road6:51
26. Test the choice, not the leaf7:09
27. Order, and bound7:26
28. The duplicate branch7:42
29. Impossible, or already walked7:58
30. Same answers, less tree8:16
31. Carry your own stack8:34
32. Nothing waiting after8:53
33. Write the loop yourself9:08
34. A stack of your own9:27
35. The resume field9:43
36. When it is worth it10:00
37. The whole thing10:18

Recursion and backtracking: trusting the smaller problem. Stand in a queue and ask how many people are ahead of you. You do not count them. You ask the person in front, and add one. The person at the very front answers zero. That is recur

Mark as watchedSaved in this browser only.