Given M binary variables and R samples, what is the maximum number of leaves in a decision tree?

The maximum possible combinations with M binary variable is

$$ 2^M $$ so essentially if all these values have different classes, then the number of leaves should be equal to

$$ if \ R<2^M => R \\ else \ 2^M $$

A tree which has all possible leaves for M binary variables could at max contain 2^M combinations, think each leaf with written value of a possible combination eg: 0000,0001,0002,...,1110,1111, and these can come only once, because only 1 label can be associated with each leaf

In case a row has multiple labels, for same set of input, the max number of leaves would be equal to unique input combinations in R

    A   B   label
0   1   0   0
1   0   0   1
2   1   1   2
3   1   1   1

The number of leaves in this case would be 3 and not 4 (number of inputs)