I'll assume you're interested in unitary, n-qubit operations. Then yes, any universal gate-set can approximate any given unitary, even though some unitaries may require an exponential number of gates for this. The Solovay-Kitaev theorem gives a constructive proof, so it gives a concrete algorithm to find a sequence of operations from the universal gate-set that approximates any given unitary to an arbitrary distance. (There are some technical requirements, such as the need for the inverse of all gates in the gate-set.)
If you're interested in exactly obtaining the unitary, then not all gate-sets are equivalent. This is the realm of quantum circuit synthesis. In this case, as in the approximate case, sometimes auxiliary qubits can decrease the gate-count or the depth of the resulting circuit. As an example, check these exact decompositions of Toffoli gates, with and without auxiliary qubits: https://arxiv.org/abs/0803.2316