If I want to obtain the SHAP values with kernel SHAP for a kNN classifier with n variables, do I have to recalculate the prediction 2^n times?
(I'm not using python, but MATLAB, so I need to know the inside of the algorithm)
Yes, I believe so according to the paper entitled 'A Unified Approach to Interpreting Model Predictions'.
You will need to iterate through all feature coalitions: hence the 2^n (where n in number of features).