This is not quite true, what you are describing is "dumb" fuzzing. Modern fuzzers are coverage guided and will search for and devote more effort to inputs which trigger new branches / paths.

https://afl-1.readthedocs.io/en/latest/about_afl.html

But yeah in general path coverage is hard and fuzzing works better if you have a comprehensive corpus of test inputs.