Java Bitmask DP
Nice problem combining multiple sub problems. The key ideas are these\n\n1. Enumerate all subtress . There are (1<<n) subtrees , since n is only 15 max this wil
Nice problem combining multiple sub problems. The key ideas are these\n\n1. Enumerate all subtress . There are (1<<n) subtrees , since n is only 15 max this will come to around 33k.\n2. For each subtree check if its valid. \n3. find the max distance between 2 nodes in the subtree essentially the diameter . \n\n```\nclass Solution {\n    int farthest = -1;\n    int maxDist = -1;\n    int pathMask = 0;\n\n    public int[] countSubgraphsForEachDiameter(int n, int[][] edges) {\n        HashMap<Integer, Set<Integer>> graph = new HashMap<>();\n        for (int[] edge : edges) {\n            edge[0]--;\n            edge[1]--;\n            Set<Integer> set = graph.getOrDefault(edge[0], new HashSet<>());\n            set.add(edge[1]);\n            graph.put(edge[0], set);\n            set = graph.getOrDefault(edge[1], new HashSet<>());\n            set.add(edge[0]);\n            graph.put(edge[1], set);\n        }\n        int[] arr = new int[n];\n        for (int i = 1; i <= (1 << n); i++) {\n            int aVertex = -1;\n            for (int j = 0; j < n; j++) {\n                if ((i & (1 << j)) > 0) {\n                    aVertex = j;\n                    break;\n                }\n            }\n            if (aVertex != -1) {\n                traverse(aVertex, graph, i, 0, 0);\n                if (pathMask != -1 && (pathMask ^ i) == 0 && farthest != -1 && maxDist >= 1) {\n                    //subtree is valid;\n                    maxDist = -1;\n                    pathMask = 0;\n                    traverse(farthest, graph, i, 0, 0);\n                    arr[maxDist]++;\n                }\n            }\n            pathMask = 0;\n            maxDist = -1;\n            farthest = -1;\n        }\n        return Arrays.copyOfRange(arr, 1, arr.length);\n    }\n\n    private void traverse(int node, HashMap<Integer, Set<Integer>> graph, int subTree, int visited, int nodeDist) {\n        pathMask |= (1 << node);\n        if (nodeDist > maxDist) {\n            maxDist = nodeDist;\n            farthest = node;\n        }\n        if ((visited & (1 << node)) == 0) {\n            visited |= (1 << node);\n            for (int child : graph.get(node)) {\n                if ((visited & (1 << child)) == 0 && ((subTree & (1 << child)) > 0)) {\n                    traverse(child, graph, subTree, visited, nodeDist + 1);\n                }\n            }\n        }\n    }\n}\n```
[]