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][1].

**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][2]. 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][3].


  [1]: http://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice
  [2]: http://stackoverflow.com/questions/28204556/pass-by-value-or-const-reference-to-function
  [3]: http://stackoverflow.com/questions/8269874/performance-difference-between-accessing-local-and-class-member-variables