LeetCode: Number of Squareful Arrays

Posted on August 5, 2019July 26, 2020 by braindenny

Number of Squareful Arrays

Similar Problems:

Given an array A of non-negative integers, the array is squareful if for every pair of adjacent elements, their sum is a perfect square.

Return the number of permutations of A that are squareful. Two permutations A1 and A2 differ if and only if there is some index i such that A1[i] != A2[i].

Example 1:

Input: [1,17,8]
Output: 2
Explanation: 
[1,8,17] and [17,8,1] are the valid permutations.

Example 2:

Input: [2,2,2]
Output: 1

Note:

1 <= A.length <= 12
0 <= A[i] <= 1e9

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

// https://code.dennyzhang.com/number-of-squareful-arrays
// Basic Ideas: graph + backtracking
//
// Notice: how to avoid duplication effectively?
//
// Complexity: Time O(N^N), Space O(1)
import ("math"
        "sort")

func dfs(pos int, edges [][]bool, visited []bool, cnt *int, res *int, A []int) {
    // get all result
    if *cnt == len(visited) {
        *res = *res + 1
        return
    }

    visited[pos] = true
    *cnt = *cnt + 1
    for n, b := range edges[pos] {
        if b && !visited[n] {
            if n>0 && A[n-1] == A[n] && !visited[n-1] {
                // no need to evaluate current one
                continue
            }
            dfs(n, edges, visited, cnt, res, A)
        }
    }
    visited[pos] = false
    *cnt = *cnt - 1
}

func numSquarefulPerms(A []int) int {
    sort.Ints(A)
    edges := make([][]bool, len(A))
    for i, _ := range edges {
        edges[i] = make([]bool, len(A))
    }
    // update edges
    for i:=0; i<len(A); i++ {
        for j:=i+1; j<len(A); j++ {
            v := A[i]+A[j]
            s := int(math.Sqrt(float64(v)))
            if s*s == v {
                edges[i][j] = true
                edges[j][i] = true
            }
        }
    }

    res := 0
    for i:=0; i<len(A); i++ {
        if i>0 && A[i] == A[i-1] {
            // avoid duplication
            continue
        }
        visited := make([]bool, len(A))
        cnt := 1
        dfs(i, edges, visited, &cnt, &res, A)
    }
    return res
}

Post Views: 0