# Confused with regsubsets() in R

I am a little confused with regsubsets in R, and the different methods- AIC, Cp and Adjusted $$R^2$$ in general. Suppose our model has $$p$$ predictors. From the output one gets from the summary, it seems that regsubsets considers every combination of $$k$$ out of $$p$$ predictors, and then spits out the best choice of $$k$$ predictors that give the lowest RSS. It does this for $$k$$ that you can select going from $$1$$ to $$p$$ - say I do this for all $$k$$ from 1 to $$p$$. Now I have $$p$$ models based on RSS alone.

When you call the AIC, Cp or Adjusted $$R^2$$ plots for this run, it gives you the $$k$$ that corresponds to the best model out of the $$p$$ models, based on the criterion called.

My question is, suppose we take AIC as our criterion - why doesn't regsubsets run $$\binom{p}{k}$$ models for each $$k$$, selecting the best $$k$$ predictors based on AIC, then run over all $$k$$ from 1 to $$p$$, and evaluate the best k based on AIC again. In other words, why is the first half done using RSS and then latter half using AIC?