0996.md

Number of Squareful Arrays

题目

An array is squareful if the sum of every pair of adjacent elements is a perfect square.

Given an integer array nums, return the number of permutations of nums that are squareful.

Two permutations perm1 and perm2 are different if there is some index i such that perm1[i] != perm2[i].

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

Example 2:
Input: nums = [2,2,2]
Output: 1
 

Constraints:

1 <= nums.length <= 12
0 <= nums[i] <= 109

思路

题意：给定一个数组，数据元素为可选集合，求满足以下条件的集合的数量
1. 任意两个相邻的元素是某个自然整数n的平方。
2. 两个结果如果排列不完全一样就是两种解。如果完全一样需要去重。

回溯法：
可选集合为通过nums和index空值，是否满足条件1可以提前计算好，相同的sum值只需要计算一次。
当前层选定了一个数之后，剩下的可选集加上当前的数就可以构成下一层的输入了。
一直dfs往下走，当可选集合为空则记为一次res。

剪枝：
1。 当前层不需要考虑相同的元素，比如当前层处理了2，以2往下层走的所有结果都已经检查过了，所以当前层再碰到2就不需要处理了。 

代码

func numSquarefulPerms(nums []int) int {
	var (
		res = 0
	)
	cache := make(map[int]bool, len(nums))
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			_, ok := cache[nums[i]+nums[j]]
			if ok {
				continue
			}
			adjSum := nums[i] + nums[j]
			temp := int(math.Sqrt(float64(adjSum)))
			if temp*temp == adjSum {
				cache[adjSum] = true
			} else {
				cache[adjSum] = false
			}
		}
	}
	dfs(nums, 0, 0, &res, cache)
	return res
}

func dfs(nums []int, index int, prevNum int, res *int, cache map[int]bool) {
	if index >= len(nums) {
		*res++
		return
	}

	for i := index; i < len(nums); i++ {
		repeat := false
		for j := index; j < i; j++ {
			if nums[i] == nums[j] {
				repeat = true
				break
			}
		}
		if repeat {
			continue
		}
		if index == 0 {
			temp := nums[i]
			nums[i], nums[index] = nums[index], nums[i]
			dfs(nums, index+1, temp, res, cache)
			nums[index], nums[i] = nums[i], nums[index]
			continue
		}
		if cache[prevNum+nums[i]] {
			temp := nums[i]
			nums[i], nums[index] = nums[index], nums[i]
			dfs(nums, index+1, temp, res, cache)
			nums[index], nums[i] = nums[i], nums[index]
		}
	}
}