While significant strides have been made in deep reinforcement learning (RL), the intricacies of combinatorial realms, such as in AI planning and scientific discovery, continue to pose formidable challenges to RL methodologies. The main difficulty in these domains is that the occurrence of a positive reward signal becomes increasingly rare as the minimal solution length or the number of states dramatically increase. In this thesis, I will describe our deep combinatorial reasoning approach for tackling challenging problems with a significant combinatorial component. I will start by describing how the approach bridges the gap between specialized AI solvers and the state-of-the-art performance achieved by humans for Sokoban, a prototypical AI planning problem. Further, I will showcase the adaptability of our framework, illustrating its application to mass spectrometry prediction and metabolite identification. In the first part of the thesis, I will delve into the enhancement of traditional best-first search with various deep reinforcement learning techniques to improve performance in Sokoban. These techniques include sub-instance creation, curriculum training, and fully differentiable search, all of which strive to minimize the disparity between learning and searching. I will exemplify how this framework surpasses the expertise of human players in tackling challenging Sokoban instances, yielding both ingenious and efficient solutions. Subsequently, I will highlight the applicability of our deep combinatorial reasoning approach within the realm of scientific discovery, with a particular emphasis on mass spectrometry prediction. Our methodology exploits a Directed Acyclic Graph (DAG) representation of the fragmentation process, which enables the learning algorithm to swiftly pinpoint a small subset of states responsible for most of the fragmentation probability. Importantly, the unraveled fragmentation path is interpretable, fostering the rediscovery of numerous chemical rules based solely on the available data. In conclusion, our deep combinatorial reasoning approach exhibits flexibility and adaptability, making it suitable for tackling a myriad of challenging combinatorial problems that require a tight integration of AI reasoning and learning.