A mi me ha ido bien de la siguiente manera.
Primero respaldo todo usando solo el pc. Asegurate de tener sincronizados los contactos ya sea en gmail, outlook u otro servicio. Si no los tienes sincronizados o no sabes puedes usar Smart Switch de samsung para un respaldo completo o selectivo.
Segundo formateo la SD desde el movil.
Tercero restauro a valores de fabrica.
Posterior a eso hay un punto no menor.
Cuando estas haciendo la configuracion inicial (post reset) te pregunta si deseas restaurar una copia de seguridad. Si lo que quieres es dejar el movil como nuevo no la uses, mas bien selecciona "configurar como telefono nuevo" o algo asi. Despues puedes ir a la biblioteca de la Play Store e instalar solo las apps que quieras.
Si tienes alguna duda me avisas
Saludos