When is it fine to use backtracking?

New / EngJesusC
Apr 15 20 Comments

Complexity of most backtracking algorithms are usually O(n!) when is it fine to use as last resort?


Want to comment? LOG IN or SIGN UP
TOP 20 Comments
  • Bloomberg ggmu1
    When n is not huge.
    Apr 151
  • Capital One public_
    When the problem says “generate all”.
    Apr 150
  • Two Sigma not nice
    When you get to a dead end
    Apr 150
  • Tableau krxi15
    OP talks like he can use backtracking at will.

    Most people can’t use it even when it’s supposed to be used.
    Apr 151
    • Yahoo / ProductVOui62
      Haha. Good one
      Apr 15
  • New / R&Dmr.jangles
    When you lose your keys
    Apr 150
  • Cisco pista
    I think when we need to get number of combinations, we can use dynamic programming. But if it comes to printing those combinations we have no choice but backtracking
    Apr 150
  • IBM / Engbbw lover
    When you want intant rejects
    Apr 150
  • Unity Lvl1Crook
    When you need to
    Apr 150
  • When you're writing C++
    Apr 150
  • Amazon KULL00
    OP what is an alternative?
    Apr 151
    • Pandora joystick
      If you are in the middle of an interview, DP most likely.
      Apr 15
  • Morgan Stanley khotaa
    When pruning paths, alpha beta pruning or some other heuristics. Or tic tac toe 😂
    Apr 150
  • Intel LvOT55
    Stepwise forward selection in machine learning (maybe)
    Apr 150
  • Google


    When you only want one solution, and there are many (e.g. N-queens problem)
    Apr 150
  • Facebook QGhE38
    Every time you need so called “dynamic programming”. Write out the backtracking code, and simply use some sort of memorization to record the duplicated state. Then it’s dynamic programming.
    Apr 150
  • Amazon bingming
    When you need the entire exhaustive search space.
    Apr 150
  • Jet.com / Other


    When you narrow down your search and look for local optimum
    Apr 150
  • New arch135
    When there is a permutation involved without any specific pattern , but with some limitation in most cases
    Apr 150

Join verified employees in our anonymous social network!Download the app!