996. Number of Squareful Arrays

T: O(n!*n)

S: O(n!*n)

class Solution {
    int res = 0;
    public int numSquarefulPerms(int[] nums) {
        int n = nums.length;
        List<Integer>[] graph = new ArrayList[n];
        boolean[] visited = new boolean[n];
        
        Arrays.sort(nums); // for 去重
        
        // build graph
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
                // 符合 Squareful 才建立邊
                int root = (int)Math.sqrt(nums[i] + nums[j]);
                if (root * root == nums[i] + nums[j]) {
                    graph[i].add(j);
                }
            }
        }
        
        // 對每點來做 dfs, 每點反覆去做, 這是起點而已, 起點的 backtracking
        for (int i = 0; i < n; i++) {
            
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            visited[i] = true;
            dfs(nums, i, 1, graph, visited);
            visited[i] = false;
        }
        return res;
    }
    // child 的 backtracking
    private void dfs(int[] nums, int start, int count, List<Integer>[] graph, boolean[] visited) {
        // count is processed node number, if all done, finished
        // 這裡用走訪過的 node 個數(count) 來判斷是不是全走完了
        if (count == nums.length) { 
            res++;
            return;
        }
        // 這一定要用 last, 因為 i > 0 並無法確保之前就有一個數, 這裡是讀取 graph 的 index (不個定)
        int last = -1;
        for (int i : graph[start]) { 
            if (visited[i]) {
                continue;
            }
            if (last == nums[i]) {
                continue;
            }
            last = nums[i];
            
            visited[i] = true;
            dfs(nums, i, count+1, graph, visited);
            visited[i] = false;
        }
    }
}