State estimation from the sparsely corrupted measurements, a combinatorial problem, has been addressed by brute force search or convex relaxations in the literature. However, the computational efficiency and estimation correctness of these methods cannot be simultaneously guaranteed. This paper studies how to relieve the computational complexity on the premise of the estimation correctness. A novel algorithm based on a constrained set partitioning approach is presented. The computational efforts are alleviated by drastically reducing the search space, and the estimation correctness is guaranteed in terms of the existence of a solution for a set of linear matrix inequalities. The theoretical results are substantiated by simulating two numerical examples.