Complex problem solving (CPS) is considered to be one of the most important skills for successful learning. In an effort to explore the nature of CPS, this study aims to investigate the role of inductive reasoning (IR) and combinatorial reasoning (CR) in the problem-solving process of students using statistically distinguishable exploration strategies in the CPS environment. The sample was drawn from a group of university students (N = 1343). The tests were delivered via the eDia online assessment platform. Latent class analyses were employed to seek students whose problem-solving strategies showed similar patterns. Four qualitatively different class profiles were identified: (1) 84.3% of the students were proficient strategy users, (2) 6.2% were rapid learners, (3) 3.1% were non-persistent explorers, and (4) 6.5% were non-performing explorers. Better exploration strategy users showed greater development in thinking skills, and the roles of IR and CR in the CPS process were varied for each type of strategy user. To sum up, the analysis identified students' problem-solving behaviours in respect of exploration strategy in the CPS environment and detected a number of remarkable differences in terms of the use of thinking skills between students with different exploration strategies.