title: How to backtrack when using a iterative DFS implemented via a stack
body: <p>I was completing this Leetcode problem: <a href="https://leetcode.com/problems/word-search/" rel="nofollow noreferrer">https://leetcode.com/problems/word-search/</a> and I randomly chose to implement the DFS iteratively with a while loop and a stack but I encountered some inconveniences when backtracking that I wouldn't normally occur if I had done the problem recursively i.e. I could only think of implementing a list (<code>visited_index</code>) to keep track of the indexes I had visited and pop values off to set the boolean matrix <code>visited</code> back to <code>False</code> when backtracking.</p>
  <pre class="lang-py prettyprint-override"><code>from collections import defaultdict
  class Solution:
      def exist(self, board: List[List[str]], word: str) -&gt; bool:
          starting_points = defaultdict(list)
          m, n = len(board), len(board[0])
          for i in range(m):
              for j in range(n):
                  starting_points[board[i][j]].append((i,j))
          
          
          start = starting_points[word[0]]
          visited = [[False] * n for _ in range(m)]
          stack = []
          directions = [(1,0), (0,-1), (-1,0), (0,1)]
          
          for s in start:
              stack.append((s[0], s[1], 0))
              visited_index = [] # EXTRA LIST USED
              while stack:
                  x, y, count = stack.pop()
                  while len(visited_index) &gt; count:
                      i, j = visited_index.pop()
                      visited[i][j] = False # SETTING BACK TO FALSE WHEN BACKTRACKING
                  if x &lt; 0 or x &gt;= m or y &lt; 0 or y &gt;= n or visited[x][y] or board[x][y] != word[count]:
                      continue
                  else:
                      
                      visited[x][y] = True
                      visited_index.append((x,y))
                      if count + 1 == len(word):
                          return True
                      for d in directions:
                          i, j = x + d[0], y + d[1]
                          stack.append((i,j, count + 1))
              
              else:
                  stack.clear()
                  for i in range(m):
                      for j in range(n):
                          visited[i][j] = False
          return False
  </code></pre>
  <p>I believe that in a recursive approach I could have reset the the <code>visited</code> boolean value back to <code>False</code> at the end of the function without the need to use an extra list. Does anyone have any suggestions to not introduce an extra data structure when doing an iterative DFS with a stack?</p>