Esta es una de las cosas que Samsung tiene que mejorar. En otras marcas se abre el bootloader se hace el acceso root y haces una copia de seguridad.
Cuando tienes un problema de estas características tan facilmcomo restaurar y comprobar si es cuestión de algún software que caude incompatibilidad o fallo del terminal.
Así si haces un Hard reset te toca instalar todo de nuevo con la pérdida de tiempo que eso supone.
Dicho esto. Intentaría recodar el momento en que te has dado cuenta y desinstalar las app a partir de ese momento con la eliminación de cache y datos antes de desinstalar. Importante.
Y a partir de aquí ir mirando y si no Hard reset.