Is it possible to do the equivalent of this with data in a worksheet?

I want to be able to select one or more values from two different columns.

For example , in a State Column, I want to be able to select NY, HI, CA
and in a Grocery Store Column, I want to be able to select, Safeway and
Lucky's

However, when I apply an advanced filter, selecting NY, HI, and CA, I find
that I am getting other Grocery stores, simply because the advanced filter
wants to give me EVERYTHING from NY, HI and CA regardless of my 2nd column
criteria.

Essentially, I want to be able to say something like State IN("NY", "HI",
"CA") AND [Grocery Store] IN("Safeway", "Lucky's")

Why can't I just hook it up to some external data - you ask? Because I
won't have the option to setup an external data source for this Application.