One could simply write the program to generate all the possible pairs in the sequence. If the sequence is 400 bases long, M could be 200. 200 is a number larger than the number of atoms in the universe. Even a supercomputer cannot do that many evaluations in a reasonable amount of time. Yet the HIV virus is 9,128 bases long.
Many interesting molecules are tens of thousands of bases long.
The practical solution makes use of a technique called dynamic programming. This means that the solution to a large problem can be decomposed into solutions to smaller problems. This approach renders the problem tractable. The original program to predict RNA molecular structure by this dynamic programming method was developed by Michael Zucker, who provided his Fortran source code to Michael Gribskov's group. The reason that the dynamic programming algorithm can be parallelized is that many of the small subproblems which go to make up the full solution can be evaluated concurrently.