The availability of single-cell transcriptomics data opens new opportunities for rational design of combination cancer treatments. Mining such data, we employed combinatorial optimization techniques to explore the landscape of optimal combination therapies in solid tumors including brain, head and neck, melanoma, lung, breast and colon cancers. We assume that each individual therapy can target any one of 1269 genes encoding cell surface receptors, which may be targets of CAR-T, conjugated antibodies or coated nanoparticle therapies. As a baseline case, we studied the killing of at least 80% of the tumor cells while sparing more than 90% of the non-tumor cells in each patient, as a putative regimen. We find that in most cancer types, personalized combinations composed of at most four targets are then sufficient. However, the number of distinct targets that one would need to assemble to treat all patients in a cohort accordingly would be around 10 in most cases. Further requiring that the target genes be also lowly expressed in healthy tissues uncovers qualitatively similar trends. However, as one asks for more stringent and selective killing beyond the baseline regimen we focused on, we find that the number of targets needed rises rapidly. Emerging individual promising receptor targets include PTPRZ1, which is frequently found in the optimal combinations for brain and head and neck cancers, and EGFR, a recurring target in multiple tumor types. In sum, this systematic single-cell based characterization of the landscape of combinatorial receptor-mediated cancer treatments establishes first of their kind estimates on the number of targets needed, identifying promising ones for future development.