Stepwise Selection
A common suggestion for avoiding the consideration of all subsets is to
use stepwise selection. There are two standard approaches:
- Forward selection. Begin by finding the best single
feature, and commit to it. In general, given a set of selected features,
add the feature that improves performance most.
- Backward elimination. From a set of remaining features,
repeatedly delete the feature that reduces performance the least.
Other optimization procedures, such as branch-and-bound, can also be used
(see Fukunaga). In addition, instead
of trying to minimize the error rate, one can minimize a related but more
easily computed criterion, such as the standardized distance between the
closest pair of means.
Of course, all of these approaches are heuristic, and there is no guarantee
that they will find the globally best subsets. However, the simpler methods
are certainly worth trying when you have an excessivley large number of
features.
Back to Exhaustive
On to Combine 
Up to Feature Selection