Categorical Variables in Decision Tree I was going through the Andrew Ng's notes for Decision Trees. It has one section explaining the usage of categorical variables using Decision Trees in which I am not able to understand this part 

" A caveat to the above is that we must take care to not allow a variable
to have too many categories. For a set of categories S, our set of possible
questions is the power set P(S), of cardinality 2^|S| . Thus, a large number of categories makes question selection computationally intractable. " 

Q1 -> How is the possible set of questions is $2^{|S|}$ ? It should be equal to the non-leaf nodes in the decision tree . 

Link to Andrew Ng notes on Decision Tree : http://cs229.stanford.edu/notes/cs229-notes-dt.pdf 

Can you please give some clarification on it .
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)}$.