Nuclear magnetic resonance (NMR) spectroscopy is widely used to determine and analyze protein structures. An essential step in NMR studies is determining the backbone resonance assignment, which maps individual atoms to experimentally measured resonance frequencies. Performing assignment is challenging owing to the noise and ambiguity in NMR spectra. Although automated procedures have been investigated, by-and-large they are still struggling to gain acceptance because of inherent limits in scalability and/or unacceptable levels of assignment error. To have confidence in the results, an algorithm should be complete, i.e. able to identify all solutions consistent with the data, including all arbitrary configurations of extra and missing peaks. The ensuing combinatorial explosion in the space of possible assignments has led to the perception that complete search is hopelessly inefficient and cannot scale to realistic datasets.