The availability of single-cell transcriptomics data opens up new opportunities for designing combination cancer treatments. Mining such data, we employed combinatorial optimization to explore the landscape of optimal combination therapies in solid tumors (including brain, head and neck, melanoma, lung, breast and colon cancers), assuming that each drug can target one of 1269 genes encoding cell surface receptors and deliver a toxin into the cell. We also identified optimal combinations among a subset of 58 genes for which targeted treatments have been already tested in vitro. We first study a personalized treatment objective, identifying optimal combinations for each patient, aimed at killing most tumor cells while sparing most non-tumor cells. We find that a single-digit number of targets is sufficient for killing at least 80% of the tumor cells while killing at most 10% of the non-tumor cells in each patient. However, with more stringent killing requirements, the number of targets required may rise sharply in some cancer types. We additionally study a fair objective, identifying an optimal treatment basket for a multi-patient cohort while bounding the number of extra treatments given to each patient. Encouragingly, we find that optimally fair combinations usually require at most three extra treatments compared to the personalized combinations. Targets appearing in many optimal solutions include PTPRZ1 (especially for brain cancer), CLDN4, CXADR, EPHB4, NTRK2, EGFR, SLC2A, ERBB3, IL17RD and EDNRB. This multi-disciplinary analysis provides the first systematic characterization of combinatorial targeted treatments for solid tumors and uncovers promising cell-surface targets for future development.