What is difference between backtracking and depth first search?

  • 1

    I know backtracking is one of depth first search, but I notice the questions under backtracking tag are quite different from DFS. After search google, I know backtracking does not keep the entire tree structure while DFS does. Could you please give me more explanation? Prefer examples. Thank you very much!

  • 0

    Difference 1:
    DFS handles an explicit tree.While Backtracking handles an implicit tree

    Difference 2:
    Depth First Search is a special type of backtracking algorithmic design paradigm where the process of backtracking takes place in the leaf nodes. In case of backtracking,the algorithm also rejects the useless branch of the state-space tree.This is why DFS maintains the entire tree structure while Backtracking maintaines a pruned tree

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.