Categorical Variables in Decision Tree
The $2^{|S|}$ number of POSSIBLE questions is defined by the number of different combinations of subsets of $S$ that could be part of the first partitions, then the second and so on until the tree is finished. That being the worst case.

Imagine that: $loc \in{} N$ is the first separation, so it's divided into Yes/No. Then $loc \in{} S$ is divided into Yes/No.

Then $loc \in{} E$ is the third partition and the answer is the same (Yes/No), you have 8 (2^3) questions asked. There are many combinations of use/no use/which to combine in which step, etc, but ultimately you will be asking the tree to consider all possibilities, which are $2^{card(S)}$.