When is it fine to use backtracking?

New / Eng JesusC
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 15 1
  • Capital One public_
    When the problem says “generate all”.
    Apr 15 0
  • Two Sigma not nice
    When you get to a dead end
    Apr 15 0
  • 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 15 1
    • Yahoo / Product VOui62
      Haha. Good one
      Apr 15
  • New / R&D mr.jangles
    When you lose your keys
    Apr 15 0
  • 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 15 0
  • IBM / Eng bbw lover
    When you want intant rejects
    Apr 15 0
  • Unity Lvl1Crook
    When you need to
    Apr 15 0
  • When you're writing C++
    Apr 15 0
  • Amazon KULL00
    OP what is an alternative?
    Apr 15 1
    • Pandora / Eng 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 15 0
  • Intel LvOT55
    Stepwise forward selection in machine learning (maybe)
    Apr 15 0
  • Google


    When you only want one solution, and there are many (e.g. N-queens problem)
    Apr 15 0
  • Facebook / Eng 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 15 0
  • Amazon / Eng bingming
    When you need the entire exhaustive search space.
    Apr 15 0
  • Jet.com / Other

    Jet.com Other

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