Update: Search for the first solution.

for a normal Depth First Search it is simple, just use a hashset

    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;
     }

However, when it becomes depth limited, i cannot simply do this

    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;
     }

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 maxdepth

How should I fix it? Would it add more space complexity to the algorithm?

Or it just doesn't require to memoize the state at all.

Update:

for example, a decision tree is the following:

   A - B - C - D - E - A
                   |
                   F - G (Goal)

Starting from state A. and G is a goal state. Clearly there is a solution under depth 3.

However, using my implementation under depth 4, if the direction of search happens to be

A(0) -> B(1) -> C(2) -> D(3) -> E(4) -> F(5) exceeds depth, then it would do back track to A, however E is visited, it would ignore the check direction A - E - F - G