Un restablecimiento de fábrica borra todos los datos en la partición de datos del usuario. En dispositivos Android con cifrado predeterminado, este proceso es irreversible. Cualquier respaldo tiene que ser realizado antes de realizar un restablecimiento de fábrica.
Si has habilitado la copia de seguridad del dispositivo en la nube de Google, entonces, por supuesto, si utilizas la misma cuenta de Google y restauras los datos desde Google Cloud, una aplicación maliciosa podría ser reinstalada. Pero eso requeriría que la aplicación esté disponible a través de Google Play Store en el momento en que inicias sesión después de un restablecimiento de fábrica. Google intenta identificar aplicaciones maliciosas y eliminarlas de Play Store, pero eso no significa que Play Store esté libre de malware al 100%.
Sin embargo, eso no significa que el malware no pueda sobrevivir a un restablecimiento de fábrica en el dispositivo en sí. Para eso, tendría que haber sido colocado en la partición del sistema u otra partición que no sea modificada por el restablecimiento de fábrica.
Dependiendo del teléfono, es probable o no que exista tal malware persistente. Si realmente crees que tu dispositivo está comprometido, entonces sólo hay una solución:
Comprar un nuevo dispositivo de un proveedor de confianza, habilitar un nuevo PIN de pantalla de bloqueo con 5 o más dígitos y que nadie que te conozca pueda adivinar (nada de cumpleaños o PIN utilizados en otro lugar).
Usar una nueva cuenta de Google con una contraseña nueva, segura y compleja. Sólo instalar aplicaciones de confianza de grandes empresas conocidas en las que confíes.
Y lo más importante, aprender cómo se comporta tu dispositivo y qué es normal. Muchos usuarios sospechan que sus dispositivos son maliciosos porque no entienden cómo funciona Android e interpretan mal el comportamiento del dispositivo.
Este sitio es un buen lugar para aprender cómo funciona Android, léelo varias veces a la semana y aprende de las preguntas y respuestas que otros usuarios publican o simplemente navega por preguntas más antiguas siempre y cuando no se trate de una versión de Android muy alejada de tu dispositivo.