Yep, "con más" means "with more" and "con menos" means "with less".
"With cheese or without?" can be "¿Con o sin queso?" or "¿Con queso o sin queso?" You would be understood if you asked "¿Con queso o sin?", but some quick corpus checking indicates that it's non-standard.
|