Java DFS O(2^20) with explanation
I spent a few minutes but I can\'t come out a workable solution until I read the constraints very carefully.\n\nAnalysis\n1. 10 <= time[j], maxTime <= 100 By th
I spent a few minutes but I can\'t come out a workable solution until I read the constraints very carefully.\n\n**Analysis**\n1. `10 <= time[j], maxTime <= 100` By this constraint, there are at most 10 nodes in a path.\n2. There are at most `four` edges connected to each node\n3. Based on the aforementioned constraints, the brute force approach runs in O(4^10) = O(2^20) which is sufficient to pass the tests.\n\n```\nclass Solution {\n    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {\n        int n = values.length;\n        List<int[]>[] adj = new List[n];\n        for (int i = 0; i < n; ++i) adj[i] = new LinkedList();\n        for (int[] e : edges) {\n            int i = e[0], j = e[1], t = e[2];\n            adj[i].add(new int[]{j, t});\n            adj[j].add(new int[]{i, t});\n        }\n        int[] res = new int[1];\n        int[] seen = new int[n];\n        seen[0]++;\n        dfs(adj, 0, values, maxTime, seen, res, values[0]);\n        return res[0];\n    }\n    private void dfs(List<int[]>[] adj, int src, int[] values, int maxTime, int[] seen, int[] res, int sum) {\n        if (0 == src) {\n            res[0] = Math.max(res[0], sum);\n        }\n        if (0 > maxTime) return;\n        for (int[] data : adj[src]) {\n            int dst = data[0], t = data[1];\n            if (0 > maxTime - t) continue;\n            seen[dst]++;\n            dfs(adj, dst, values, maxTime - t, seen, res, sum + (1 == seen[dst] ? values[dst] : 0));\n            seen[dst]--;\n        }\n    }\n}\n```
['Depth-First Search', 'Java']