Summary: On-shell constructibility is redefining our understanding of perturbative quantum field theory. The tree-level S-matrix of constructible theories is completely determined by a set of recurrence relations and a reduced number of scattering amplitudes. In this paper, we revisit the on-shell constructibility of gravitational theories making use of new results on soft theorems and recurrence relations. We show that using a double complex shift and an all-line soft deformation allows us to relax the technical conditions for constructibility, in order to include more general propagators and higher-derivative interactions that prevent using conventional Britto-Cachazo-Feng-Witten (BCFW) shifts. From this result we extract a set of criteria that guarantee that a given gravitational action has the same tree-level S-matrix in Minkowski spacetime as general relativity, which implies the equivalence at all orders in perturbation theory between these classical field theories on asymptotically flat spacetimes. As a corollary we deduce that the scattering amplitudes of general relativity and unimodular gravity are the same for an arbitrary number of external particles (as long as the S-matrix of the latter is unitary), thus extending previous works that were able to deal only with \(n=4\) and \(n=5\) amplitudes.