func makesquare(nums []int) bool {
n := len(nums)
if n < 4 || _sum(nums) % 4 != 0 {
return false
}
sort.Slice(nums, func(i, j int) bool { // 从大到小排列
return nums[i] > nums[j]
})
state := make([]bool, n) // 每根火柴是否被用过
return dfs(0, 0, _sum(nums) / 4, 0, nums, state)
}
func _sum(nums []int) (res int) {
for _, v := range nums {
res += v
}
return
}
/*
k: 目前已经凑好的边数
cursum: 目前在拼的这条边已经拼好了多长
target：目标边长
start: 搜索火柴的起始下标
返回值：从当前状态开始搜索，是否能拼成正方形
*/
func dfs(k, cursum, target, start int, nums []int, state []bool) bool {
if k == 4 {
return true
}
if cursum == target {
return dfs(k+1, 0, target, 0, nums, state)
}
for i:=start; i<len(nums); i++ {
if state[i]==false && nums[i] + cursum <= target {
state[i] = true
// 继续拼这条边，从当前火柴的下一个开始搜索就好，因此start=i+1
if dfs(k, nums[i] + cursum, target, i + 1, nums, state)==true {
return true
}
state[i] = false
}
}
return false
}
