Skip to main content

backtracking

Backtracking#

  • Mark the current cell position in the grid as visited and recur in the 4 possible directions. After recurring, again mark the position as unvisited. Once porblem solution is found, return true.
visitedPath.add(currentCell)// exploring all optionsconst found = backtrack(r + 1, c, idx + 1) || backtrack(r - 1, c, idx + 1) || backtrack(r, c + 1, idx + 1) || backtrack(r, c - 1, idx + 1)visitedPath.delete(currentCell)return found

  • These problems can only be solved by trying every possible configuration and each configuration is tried only once. A Naive solution for these problems is to try all configurations and output a configuration that follows given problem constraints. Backtracking works incrementally and is an optimization over the Naive solution where all possible configurations are generated and tried. see this to undertsnad - <https://www.geeksforgeeks.org/n-queen-problem-backtracking-3/>

  • Use Topological sort when there are intervals defined - https://www.geeksforgeeks.org/topological-sorting/ youtube - https://www.youtube.com/watch?v=GYmq98CVm2c&ab_channel=Insidecode

    • DAG (directed acyclic graph)
const graph = {  'A': ['B', 'C'],  'B': ['D'],  'C': ['D'],  'D': ['E'],  'E': []};
  • A set can be used to store visited paths or a matrix with boolean varaible with coordinate