title: How to store visited states in iterative deepening / depth limited search?
body: <h3>Update: Search for the first solution.</h3>
  
  <p>for a normal Depth First Search it is simple, just use a hashset</p>
  
  <pre><code>    bool DFS (currentState) =
      {
            if (myHashSet.Contains(currentState))
            {
                 return;
            }
            else
            {
                  myHashSet.Add(currentState);
            }
            if (IsSolution(currentState) return true;         
            else
            {
                for (var nextState in GetNextStates(currentState))
                     if (DFS(nextState)) return true;
            }
            return false;
       }
  </code></pre>
  
  <p>However, when it becomes depth limited, i cannot simply do this</p>
  
  <pre><code>    bool DFS (currentState, maxDepth) =
      {
            if (maxDepth = 0) return false;
            if (myHashSet.Contains(currentState))
            {
                 return;
            }
            else
            {
                  myHashSet.Add(currentState);
            }
            if (IsSolution(currentState) return true;         
            else
            {
                for (var nextState in GetNextStates(currentState))
                     if (DFS(nextState, maxDepth - 1)) return true;
            }
            return false;
       }
  </code></pre>
  
  <p>Because then it is not going to do a complete search (in a sense of always be able to find a solution if there is any) before <code>maxdepth</code></p>
  
  <p>How should I fix it? Would it add more space complexity to the algorithm?</p>
  
  <p>Or it just doesn't require to memoize the state at all.</p>
  
  <h3>Update:</h3>
  
  <p>for example, a decision tree is the following:</p>
  
  <pre><code>   A - B - C - D - E - A
                     |
                     F - G (Goal)
  </code></pre>
  
  <p>Starting from state A. and G is a goal state. Clearly there is a solution under depth 3.</p>
  
  <p>However, using my implementation under depth 4, if the direction of search happens to be</p>
  
  <p><code>A(0) -&gt; B(1) -&gt; C(2) -&gt; D(3) -&gt; E(4) -&gt; F(5)</code> exceeds depth, then it would do back track to <code>A</code>, however <code>E</code> is visited, it would ignore the check direction <code>A - E - F - G</code></p>