Uniformly and randomly choose M elements from N elements - confused

I understand similar questions have been asked like

Choose m elements randomly from a vector containing n elements

pick N items at random

But the more I look the more I got confused.

Uniformly and randomly choose M elements from N elements

So I need to pick M elements from N ones. And also I need to make the probability of being selected to be uniformly distributed for every element: $\frac{M}{N}$

My intuition was

1. Randomly choose an element


2. Get it out


3. Repeat the process on the rest of elements

I guess this solution is wrong? The probabilities for the M selected elements are $ 1/N $, $ 1/(N-1) $, ..., $ 1/(N-M) $, not $ M / N $, am I correct?

---

A possible correct solution is that

1. Just do a shuffle on the whole N elements


2. Pick the top M ones.

But I can't figure out the probability of being selected for each element.

Can anyone demonstrate the probability of this solution is $ M / N $ indeed?

---

Also of course we can use Reservoir sampling, and its probability is $ M / N $.