This paper is concerned with the number of solution to sparse signal recovery problem based on linear measurements, which is an important problem in signal processing. In the noiseless measurement case, by taking advantage of the combinatorial analysis method, an upper bound is established for the number of solution to the sparse signal recovery problem, and by constructing a special linear measuring matrix, the best of the upper bound is proved as well. Moreover, if the measuring matrix satisfies some conditions, the upper bound could be improved. Based on these results, some new ideas of a finite search can be employed to solve the sparse signal recovery problem in some special cases.