Discrete choice problems with complementarities are prevalent in economics but the large dimensionality of potential solutions substantially limits the scope of their application. We define and characterize a general class that we term combinatorial discrete choice problems and show that it covers many existing problems in economics and engineering. We propose single crossing differences (SCD) as the sufficient condition to guarantee that simple recursive procedures can find the global maximum. We introduce an algorithm motivated by this condition and show how it can be used to revisit problems whose computation was deemed infeasible before. We finally discuss results for a class of games characterized by these sufficient conditions.