Exploration of the low-lying structures of atomic or molecular clusters remains a fundamental problem in nanocluster science. Basin hopping is typically employed in conjunction with random motion, which is a perturbation of a local minimum structure. We have combined two different sampling technologies, "random sampling" and "compressed sampling", to explore the potential energy surface of molecular clusters. We used the method to study water, nitrate/water, and oxalate/water cluster systems at the MP2/aug-cc-pVDZ level of theory. An isomer of the NO3-(H2O)(3) cluster molecule with a 3D structure was lower in energy than the planar structure, which had previously been reported by experimental study as the lowest-energy structure. The lowest-energy structures of the NO3-(H2O)(5) and NO3-(H2O)(7) clusters were found to have structures similar to pure (H2O)(8) and (H2O)(10) clusters, which contradicts previous experimental result by Wang et al.(J. Chem. Phys. 2002, 116, 561-570). The new minimum energy structures for C2O42-(H2O)(5) and C2O42-(H2O)(6) are found by our calculations