I find the notion of combinatorial proofs very difficult, I was hoping someone could try to explain a particular problem in different words for me, in hope that I will finally understand the notion at work.

Give a combinatorial proof that C(n, r) = C(n, n - r).

Proof:

Suppose that S is a set with n elements.

Every subset A of S with r elements corresponds to a subset of S with n - r elements, namely the complement of A.

Thus C(n, r) = C(n, n - r).

I don't understand this proof. I have no trouble at all seeing it with algebra, but I don't understand how this proof supposedly "counts" that the LHS is equal to what the RHS counts.

Why is it that every subset A of S with r elements corresponds to a subset of S with n - r elements? How does this trivial proof show this fact?