Backtracking es una versión de depth-first que aplica el criterio LIFO para generar más que para expander. Esto es, sólo se genera un sucesor a la vez.
Su gran ventaja es su ahorro en memoria. Su gran desventaja es el no poder incluir información para evaluar cual de los sucesores es el mejor.
Algunas modificaciones de backtracking regresan al nodo que ocaciona que se llegue a un punto sin salida (dependency directed backtracking).
Backtracking también puede servir para problemas de (semi-)optimización. Si mantenemos la solución más barata hasta el momento y usamos esa información para cortar caminos (asumiendo que el costo no decrece con la profunidad de la búsqueda).