# 2065. Maximum Path Quality of a Graph
###### tags: `Leetcode` `Hard` `Backtracking` `DFS`
Link: https://leetcode.com/problems/maximum-path-quality-of-a-graph/
## 思路
题意的约束中给出了```10 <= timej, maxTime <= 100```，这说明最多只能走10步。又因为There are at most four edges connected to each node，每一步出发最多只有四种选择，所以可以用backtracking穷举
由于quality是算所有unique node的quality之和 所以用set记录之前用过的node (也可以用array)
不能发现现在的node之前用过就不往下走了因为说不定可能有别的分支还没遍历
## Code

class Solution {
    int maxQ = 0;
    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
        List<List<int[]>> graph = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();
        for(int i=0; i<values.length; i++) graph.add(new ArrayList<>());
        for(int[] edge:edges){
            graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
            graph.get(edge[1]).add(new int[]{edge[0], edge[2]});
        }
        maxQ = values[0];
        backtracking(values, graph, maxTime, visited, 0, 0, 0);
        return maxQ;
    }
    private void backtracking(int[] values, List<List<int[]>> graph, int maxTime, Set<Integer> visited, int currTime, int currQ, int currNode){
        if(currTime>maxTime) return;
        if(currNode==0){
            maxQ = Math.max(maxQ, currQ);
        }
        for(int[] next:graph.get(currNode)){
            if(!visited.contains(next[0])){
                visited.add(next[0]);
                backtracking(values, graph, maxTime, visited, currTime+next[1], currQ+values[next[0]], next[0]);
                visited.remove(next[0]);
            }
            else{
                backtracking(values, graph, maxTime, visited, currTime+next[1], currQ, next[0]);
            }
        }
    }
}