title: Intuition behind using backtracking (and not DFS)
body: <p>I am solving <a href="https://leetcode.com/problems/word-search/description/" rel="nofollow noreferrer">Word Search</a> question on LeetCode.com:</p>
  <blockquote>
  <p>Given a 2D board and a word, find if the word exists in the grid.</p>
  <p>The word can be constructed from letters of sequentially adjacent cell, where &quot;adjacent&quot; cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.</p>
  </blockquote>
  <p>The solution which I wrote with online help is as follows:</p>
  <pre><code>class Solution {
  public:
      
      //compare this with Max Area of Island:
      //they 'look' similar, but this one uses a backtracking approach since we retract when we don't find a solution
      //In case of Max Area Of Island, we are not 'coming back' - technically we do come back due to recursion, but we don't track     
      //that since we don't acutally intend to do anything - we are just counting the 1s.
      
      bool exist(vector&lt;vector&lt;char&gt;&gt;&amp; board, string&amp; word) {
          if(board.empty()) return false;
          
          for(int i=0; i&lt;board.size(); i++) {
              for(int j=0; j&lt;board[0].size(); j++) {
                  //if(word[0] == board[i][j])
                      if(existUtil(board, word, i, j, 0))    //matching the word[i][j] with 0th character of word
                          return true;
              }
          }
          
          return false;
      }
      
      bool existUtil(vector&lt;vector&lt;char&gt;&gt;&amp; board, string&amp; word, int i, int j, int match) {
          if(match==word.size()) return true;
          if(i&lt;0 || i&gt;=board.size() || j&lt;0 || j&gt;=board[0].size()) return false;
          if(board[i][j]!=word[match]) return false;
          
          board[i][j] = '*';
          bool ans = existUtil(board, word, i+1, j, match+1) || //[i+1,j]
                 existUtil(board, word, i-1, j, match+1) || // [i,j+1]
                 existUtil(board, word, i, j+1, match+1) || // [i-1,j]
                 existUtil(board, word, i, j-1, match+1);   // [i,j-1]
          board[i][j] = word[match];
          
          return ans;
      }
  };
  </code></pre>
  <p>My question is simple - why are we using a backtracking approach and not just a conventional DFS?  Pretty similar to what we have done, we could start at each character and do a DFS to determine if we could find the target word.  But we are not doing so, why?</p>
  <p>I thought a lot about it and came with the following reasoning, but I am not sure - we use a backtracking approach because of <em>the same letter cell may not be used more than once.</em>  So, when we are do backtracking, we replace the original character with a '*' and then later re-substitute it when we come back.  But this somehow does not feel right, because we could have used a <code>visited</code> matrix instead.</p>