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*

  • 1
  • 5
    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.
  • 2
    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.
  • 0
    @Fast-Nop I thought that was branch and bound.

    Back tracking is about building a solution from the recursion tree, no?
  • 0
    @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.
Your Job Suck?
Get a Better Job
Add Comment