Breadth-First Search heuristics to find solution to Water Jug Challenge
I think that the function that computes new states could be simplified in this way:

vector &lt;pair&lt;int,int&gt; &gt; newStatesSet(pair&lt;int,int&gt; state){
  //generating all possible states from a given initial state
  vector&lt;pair&lt;int,int&gt; &gt; newStates;

  if (state.first &lt; 3) {
    newStates.push_back(make_pair(3, state.second));
  }
  if (state.second &lt; 4) {
    newStates.push_back(make_pair(state.first, 4));
  }
  if (state.first &gt; 0) {
    newStates.push_back(make_pair(0, state.second));
  }
  if (state.second &gt; 0) {
    newStates.push_back(make_pair(state.first, 0));
  }
  if (state.second &gt; 0 &amp;&amp; state.first &lt; 3) {
    newStates.push_back(make_pair(std::min(3, state.first + state.second),
                        std::max(state.second - (3 - state.first), 0)));
  }
  if (state.first &gt; 0 &amp;&amp; state.second &lt; 4) {
    newStates.push_back(make_pair(std::max(state.first - (4 - state.second), 0),
                        std::min(4, state.second + state.first)));
  }

  return newStates;
}


Note that with this function a new state is generated from the previous state by considering a single operation. So, for instance, from the state (0, 0) it produces (3, 0) and (0, 4), but not (3, 4) (which will be generated later) as in your function. I think that this reflect more correctly the idea that each state is derived from the previous one with a single step.