This problem is even more complex than you're making it out to be since it could be possible that I select something in step 1 for which I will never get any result, but there is data in step 2, 3 and 4. However, whatever I select over there, I'll always get "no results".
So what you want to do is for each option in each step, look ahead all other steps until the end to see if the options could lead somewhere, which is indeed a hell of a job.
This is one of the cases I would actually consider adding redundant data to the database; on each item store whether it should be visible or not.
To get these values, start at level 4: if there are no children, set visible to 0, otherwise set visible to 1
Then goto step 3: if there are no children or all children have visible=0, set visible to 0, otherwise set visible to 1
Then do the same in step 1 and step 2 as you did in step 3.
When you show the options, only show the options that have visible = 1
Lastly, every time the data changes, recalculate the visible fields (which you can do more intelligently than just walking over all items every time!)
Like I said above, the visible field holds redundant data, but it's a heck of a lot faster to calculate it every once in a while then to calculate it on each and every step.
So IMO the redundancy is worth it.