test.java

import java.util.ArrayList;
import java.util.List;

public class test {

    public static void main(String... args) {

        int[][] g = new int[][]{
                new int[]{},
                new int[]{2, 5, 4},
                new int[]{1, 3, 4, 5, 6},
                new int[]{2, 5, 6},
                new int[]{1, 2, 5, 8, 7},
                new int[]{1, 2, 3, 4, 6, 7, 8, 9},
                new int[]{2, 3, 5, 8, 9},
                new int[]{4, 5, 8},
                new int[]{7, 4, 5, 6, 9},
                new int[]{8, 5, 6}
        };
        ArrayList<List<Integer>> res = new ArrayList<>();

        for (int i = 1; i < 10; i++) {
            dfs(g, i, new ArrayList<>(), res, new boolean[11]);
        }
        System.out.println(res);

    }

    private static void dfs(int[][] graph, int ind, List<Integer> current, List<List<Integer>> result, boolean[] vis) {
        vis[ind] = true;
        current.add(ind);

        result.add(new ArrayList<>(current));

        for (int i = 0; i < graph[ind].length; i++) {
            if (vis[graph[ind][i]]) {
                continue;
            }
            dfs(graph, graph[ind][i], current, result, vis);
        }
        vis[ind] = false;
        current.remove(current.size() - 1);
    }
}