Most problems could, in principle, be formulated in either state space or problem reduction terms. However, usually one way of formulating the problem will be be more natural and mroe efficient. The appropriate technique depends both on the nature of the solution to the problem, and on the most natural way to go about solving it.
Generally speaking, state space search may be good when the solution to a problem is naturally expressed in terms of either a final state, or a path from an initial state to a final state. We also need to be able to define rules for transforming one state into another, based on available actions in the domain. Problem reduction may be better if it is easy to decompose a problem into independent subproblems - we would have to define rules to do this. It may also allow a more natural explanation of the decision making process which allowed you to arrive at a solution, and may result in less search than state-space approaches (so may be better for very complex problems).