We obtain a necessary and sufficient condition under which random-coefficient discrete choice models such as the mixed logit models are rich enough to approximate any nonparametric random utility models across choice sets. The condition turns out to be very simple and tractable. When the condition is not satisfied and, hence, there exists a random utility model that cannot be approximated by any random-coefficient discrete choice model, we provide algorithms to measure the approximation errors. After applying our theoretical results and the algorithms to real data, we find that the approximation errors can be large in practice.