El backtracking es una técnica de resolución de problemas que consiste en generar todas las soluciones posibles que podría tener un problema e ir eliminando aquellas que cominecen a generar resultados que no resuelven el problema.
Se distingue de la Recursividad, ya que esta busca generar absolutamente todos los resultados aunque no lleguen a una solución. De esta forma se optimiza el tiempo y evitamos el uso de memoria y procesamiento innecesario.
Ejemplo: Encontrar todas las soluciones posibles para el siguiente sudoku:
En general, la complejidad temporal de los algoritmos de este tipo llegan a ser exponenciales o incluso factoriales. Sin embargo, esta se reduce gracias a la eliminación de ramas innecesarias.
