Let $S$ be a finite set and $f \colon S \to S$ be an arbitrary function. How can we find all functions $g \colon S \to S$ with $f = g \circ g$?

If $f$ and $g$ are both required to be invertible, the question is simple (but not completely trivial).

I know also about versions of this question where $S = \mathbb C$ or $\mathbb R$ and $f$ and $g$ are at least continuous, but this changes the question to something completely different.

(And is there an easy method to check whether $f$ has a square root?)