Backtracking in Graph with Comments
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(n * (2^n))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n        def dfs(curr, quality, remain):\n            nonlocal res\n\n            # base; stop as the current path is not feasible\n            if remain < 0:\n                return \n\n            # action; at node 0, update the res\n            if curr == 0:\n                res = max(res, quality)\n\n            for neigh, time in adj[curr]:\n                # update possible remain value\n                new_remain = remain - time\n\n                # neigh never seen before\n                if neigh not in visited:\n\n                    # mark as seen\n                    visited.add(neigh)\n\n                    new_quality = quality + values[neigh]\n\n                    # recur on neigh\n                    dfs(neigh, new_quality, new_remain)\n\n                    # revert back seen\n                    visited.remove(neigh)\n                \n                # neigh seen before\n                else:\n                    # recur on neigh\n                    dfs(neigh, quality, new_remain)\n        \n        # 1. build a bidirectional adjacency list\n        adj = defaultdict(list)\n        for src, des, time in edges:\n            adj[src] += [(des, time)]\n            adj[des] += [(src, time)]\n           \n        res = 0 \n\n        # 2. mark node 0 as seen\n        visited = set([0])      # trace back the visited nodes\n\n        # 3. run dfs starting at node 0\n        dfs(0, values[0], maxTime)\n\n        return res\n```
['Array', 'Backtracking', 'Depth-First Search', 'Graph', 'Recursion', 'Python', 'Python3']