Combinatorial problems arising in puzzles, origami, and (meta)material design have rare sets of solutions, which define complex and sharply delineated boundaries in configuration space. These boundaries are difficult to capture with conventional statistical and numerical methods. Here we show that convolutional neural networks can learn to recognize these boundaries for combinatorial mechanical metamaterials, down to finest detail, despite using heavily undersampled training sets, and can successfully generalize. This suggests that the network infers the underlying combinatorial rules from the sparse training set, opening up new possibilities for complex design of (meta)materials.