private static int[][] adjacencyMatrix;
    private static int[] visitedCities;
    private static int[] bestPath;

    private static int numberOfCities;
    private static int bestDistance;

    /* Depth-first Search */
    /*
     * 10 cities:
     * - without cut : 133
     * - with cut : 32
     */
    public static int[] dfs(int[][] adjacencyMatrix){

        TSP.adjacencyMatrix = adjacencyMatrix;

        numberOfCities = adjacencyMatrix.length;

        visitedCities = new int[numberOfCities];

        bestDistance = Integer.MAX_VALUE;

        // +1 because in the end we have to put 0 again
        bestPath = new int[numberOfCities + 1];

        dfsSearch(0,0,0);

        return bestPath;
    }

    private static void dfsSearch(int cityIndex, int amountOfCitiesPassed, int passedDistance) {

        // Add current city to visited list
        visitedCities[amountOfCitiesPassed] = cityIndex;

        // If amount of cities passed is number of all cities - 1
        // then it means that all cities are visited and we have to go back to start
        if (amountOfCitiesPassed == (numberOfCities - 1)) {

            int wholeTripLength = passedDistance + adjacencyMatrix[cityIndex][0];

            if (wholeTripLength < bestDistance) {
                bestDistance = wholeTripLength;

                // Create best path from visited cities
                System.arraycopy(visitedCities, 0, bestPath, 0, visitedCities.length);

                // Add going back to 0 into path
                bestPath[numberOfCities] = 0;

            }

        } else  {
            // Loop over rows
            for(int next = 0; next < numberOfCities; next++) {

                // If current passed length + length to next city is smaller than
                // current best distance.
                if (passedDistance + adjacencyMatrix[cityIndex][next] < bestDistance) {

                    // Check if 'next' is already visited
                    boolean isPassed = false;
                    for (int i = 0; i < amountOfCitiesPassed + 1; i++){
                        if (visitedCities[i] == next) {
                            isPassed = true;
                            break;
                        }
                    }

                    if (!isPassed) {
                        dfsSearch(next,
                                amountOfCitiesPassed + 1,
                                passedDistance + adjacencyMatrix[cityIndex][next]);
                    }
                }
            }
        }
    }