I have not checked your code for correct output, just for coding-related issues. Here are some comments.

Avoid using std

• Nix using namespace std. Read up on the rationale here.

Pre-allocate vector size when you know roughly how large it will be

• Rather than rushing a number of push_back operations when you know how many, or roughly how many, you will need, preallocate the vector first. In newStatesSet you know the size you will make vector newStates so you should call reserve after the declaration and before you start your push_backs. Otherwise the vector likely has to relocate after the first 2 pushes (std::vector tends to double each time memory must be reallocated, so you'll usually go from 2 to 4 to 8 and so on....)

Brevity

• You can shorten checkGoal like so:

  bool checkGoal(pair<int,int> x,int sum){ return (x.second==sum); }

  Also consider restructuring the arguments to take x.second directly as an int value parameter rather than unnecessarily passing the whole pair. Both these adjustments should improve performance as well as code readability.

Avoid side effects

• reverseTraversal is a void that makes some changes to state and also prints something out. You generally want to do one or the other in a function. It's best not to have print statements scattered throughout functions.

Additional Possible improvements:

Reference to const can be better than passing by value

• Since you don't seem to manipulate your input parameter in newStatesSet, you should consider passing it by reference to const rather than by value. I may be wrong that this would improve performance since a pair of ints shouldn't be that large, but you can benchmark to confirm.

Try making local copies of oft-used class members

• Looking at newStatesSet, I think you might consider making a local variable copy of state.first and state.second since you access them often. Whether this improves performance is compiler dependent.

I have not checked your code for correct output, just for coding-related issues. Here are some comments.

Avoid using std

• Nix using namespace std. Read up on the rationale here.

Pre-allocate vector size when you know roughly how large it will be

• Rather than rushing a number of push_back operations when you know how many, or roughly how many, you will need, preallocate the vector first. In newStatesSet you know the size you will make vector newStates so you should call reserve after the declaration and before you start your push_backs. Otherwise the vector likely has to relocate after the first 2 pushes (std::vector tends to double each time memory must be reallocated, so you'll usually go from 2 to 4 to 8 and so on....)

Brevity

• You can shorten checkGoal like so:

  bool checkGoal(pair<int,int> x,int sum){ return (x.second==sum); }

  Also consider restructuring the arguments to take x.second directly as an int value parameter rather than unnecessarily passing the whole pair. Both these adjustments should improve performance as well as code readability.

Avoid side effects

• reverseTraversal is a void that makes some changes to state and also prints something out. You generally want to do one or the other in a function. It's best not to have print statements scattered throughout functions.

Additional Possible improvements:

Reference to const can be better than passing by value

• Since you don't seem to manipulate your input parameter in newStatesSet, you should consider passing it by reference to const rather than by value. I may be wrong that this would improve performance since a pair of ints shouldn't be that large, but you can benchmark to confirm.

Try making local copies of oft-used class members

• Looking at newStatesSet, I think you might consider making a local variable copy of state.first and state.second since you access them often. Whether this improves performance is compiler dependent.