# Backtracking



## schlelia (28. Nov 2021)

Hallo,
ich hab leider (nochmal) etwas (Verständnis-)Probleme bei einer Aufgabe. Diesemal geht es ums Backtracking:

Es sind noch folgende Methode gegeben:

append(int[] prefix, int i) : Hängt ein int an ein Array hinten an
prepend(int i, int[] suffix) : Hängt ein int vorne an das Array
append(int[][] prefix, int[] is) : Hängt ein Array an ein Array hinten an
prepend(int[] is, int[][] suffix) : Hängt ein Array vorne an das Array
isValid(char[] ps) : Checkt ob die Klammerungen richtig sind, also wenn es genausoviele linke wie rechte Klammern gibt wird true returnt.
Die Idee dahinter ist natürlich Backtracking. Das heißt also ich versuche alle möglichen Entfernungen durch und schau dann eben was am kürzesten ist. Meine erste Idee war es natürlich rekursiv das Array durchzugehen. Aber wie soll ich das genau tun? Ich hab ja keinen Index i in der Methode, der mir angibt an welcher Stelle ich bin bzw. den ich im Rekursionschritt verändern könnte. Also ich gehe das Array durch und entferne das Element (mache einen Eintrag im neuen in[][] array), falls das isValid ist breche ich ab, falls nicht gehe ich eben weiter alle möglichen Lösungen durch und prüfe immer wieder ob es isValid ist.
Ich weiß leider nur nicht wo ich so recht anfangen soll.


----------

