Problema en ejercicio de backtracking

[xXJoSe13Xx]

Estoy realizando el problema de la imagen de abajo en java, mediante backtracking ( no optimo), pero cuando lo ejecuto me sale Exception in thread "main" java.lang.StackOverflowError. Y por mucho que mire no encuentro el error. Este mismo problema me ha salido sin hacerlo recursivo y no me salia ningún error, pero nos obligan a ponerlo de forma recursiva, quizás el problema es que estoy haciendo mal el backtracking, pero creo que el código, si me mira todas las soluciones.
Ademas después tengo que realizar el mismo problema pero de forma optima.






Dentro de confcomputadores no me dejan añadir nada a parte de tiempos y T