Views exposed filter selection
From what you're describing it sounds like you need Faceted search. I'm not sure if Views filters can give you the functionality you're looking for. 

Have a look at the Search Api module, it provides faceted search widgets which behave the way you described.

https://drupal.org/project/search_api