We present a new approach to gravitational lens mass map reconstruction. Our mass map solutions perfectly reproduce the positions, fluxes, and shears of all multiple images, and each mass map accurately recovers the underlying mass distribution to a resolution limited by the number of multiple images detected. We demonstrate our technique given a mock galaxy cluster similar to Abell 1689, which gravitationally lenses 19 mock background galaxies to produce 93 multiple images. We also explore cases in which as few as four multiple images are observed. Mass map solutions are never unique, and our method makes it possible to explore an extremely flexible range of physical (and unphysical) solutions, all of which perfectly reproduce the data given. Each reconfiguration of the source galaxies produces a new mass map solution. An optimization routine is provided to find those source positions (and redshifts, within uncertainties) that produce the 'most physical' mass map solution, according to a new figure of merit developed here. Our method imposes no assumptions about the slope of the radial profile or mass following light. However, unlike 'nonparametric' grid-based methods, the number of free parameters that we solve for is only as many as the number of observable constraints (or slightly greater if fluxes are constrained). For each set of source positions and redshifts, mass map solutions are obtained 'instantly' via direct matrix inversion by smoothly interpolating the deflection field using a recently developed mathematical technique. Our LensPerfect software is straightforward and easy to use, and is publicly available on our Web site.