Integrating the partials is a good idea.
In two dimensions for example, we want to find a function V(x,y) such that
\frac{\partial V}{\partial x} = g_1(x,y)
and
\frac{\partial V}{\partial y} = g_2(x,y)
We can integrate the first equation w.r.t. x and the second w.r.t. y and get by the fundamental theorem of calculus
V(x,y) = \int g_1(x,y)dx + F(y)
V(x,y) = \int g_2(x,y)dy + G(x)
The constant of integration when you integrate w.r.t. x is really an arbitrary function of y, and vice versa. (here the integration is really just any choice of antiderivative that you want, because we're writing out the constant of integration explicitly). So we're set as long as we can find functions G(x) and F(y) such that
\int g_1(x,y)dx + F(y)=\int g_2(x,y)dy + G(x)
So the question boils down to why do these functions F and G exist given the condition on the partial derivatives of g1 and g2?