473. Matchsticks to Square #

题目 #

You are given an integer array matchsticks where matchsticks[i] is the length of the ith matchstick. You want to use all the matchsticks to make one square. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Return true if you can make this square and false otherwise.

Example 1:

Input: matchsticks = [1,1,2,2,2]
Output: true
Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.

Example 2:

Input: matchsticks = [3,3,3,3,4]
Output: false
Explanation: You cannot find a way to form a square with all the matchsticks.

Constraints:

• 1 <= matchsticks.length <= 15
• 0 <= matchsticks[i] <= 109

题目大意 #

现在已知小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

解题思路 #

• 将火柴拼成一个正方形，可以将它们分成四组，每一根火柴恰好属于其中的一组；并且每一组火柴的长度之和都相同，等于所有火柴长度之和的四分之一。
• 考虑暴力解法，使用深度优先搜索枚举出所有的分组情况，并对于每一种情况，判断是否满足上述的两个条件(每根火柴属于其中一组，每组火柴长度之和相同)。依次对每一根火柴进行搜索，当搜索到第 i 根火柴时，可以考虑把它放到四组中的任意一种。对于每一种放置方法，继续对第 i + 1 根火柴进行深搜。当我们搜索完全部的 N 根火柴后，再判断每一组火柴的长度之和是否都相同。

代码 #

package leetcode

import "sort"

func makesquare(matchsticks []int) bool {
	if len(matchsticks) < 4 {
		return false
	}
	total := 0
	for _, v := range matchsticks {
		total += v
	}
	if total%4 != 0 {
		return false
	}
	sort.Slice(matchsticks, func(i, j int) bool {
		return matchsticks[i] > matchsticks[j]
	})
	visited := make([]bool, 16)
	return dfs(matchsticks, 0, 0, 0, total, &visited)
}

func dfs(matchsticks []int, cur, group, sum, total int, visited *[]bool) bool {
	if group == 4 {
		return true
	}
	if sum > total/4 {
		return false
	}
	if sum == total/4 {
		return dfs(matchsticks, 0, group+1, 0, total, visited)
	}
	last := -1
	for i := cur; i < len(matchsticks); i++ {
		if (*visited)[i] {
			continue
		}
		if last == matchsticks[i] {
			continue
		}
		(*visited)[i] = true
		last = matchsticks[i]
		if dfs(matchsticks, i+1, group, sum+matchsticks[i], total, visited) {
			return true
		}
		(*visited)[i] = false
	}
	return false
}