How do you learn to write a backtracking algo without having an existential crisis? I feel like whenever I see a problem that could use backtracking, I’m like “Looks like a case for backtracking!” *writes seven functions to try to piece it apart, gets no closer to solution, dies inside*

FIRST!

I struggled for years with "backtracking" until recently when I finally realized it's just means forked recursion -_-

I hate it when terminology gets in the way.

It's just using recursion to walk over a tree, depth first, and aborting a branch if it becomes clear that it won't contain a solution.

@Fast-Nop I thought that was branch and bound.

Back tracking is about building a solution from the recursion tree, no?

@beegC0de well you traverse your tree, and when you're at a point where you know that no sub-tree can have a solution, you track back to the node before and try its next child-node, i.e. you enter a sibling node. Or, if there is no further sibling node, you instead track back to the level above.

Of course, you can also drop the evaluation whether a branch can even have a solution, then you will traverse the whole tree - but that will have worse performance than cutting off branches where no cherries are hanging anyway.