473. Matchsticks to Square

Problem

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

Problem Summary

Given the number of matchsticks the little girl has, find a way to use all the matchsticks to form a square. You cannot break the matchsticks, but you can connect them, and every matchstick must be used. The input is the number of matchsticks the little girl has, with each matchstick represented by its length. The output is whether all the matchsticks can be used to form a square.

Solution Ideas

• To form a square with the matchsticks, they can be divided into four groups, with each matchstick belonging to exactly one group; and the sum of the lengths of the matchsticks in each group must be the same, equal to one fourth of the total length of all matchsticks.
• Consider a brute-force solution: use depth-first search to enumerate all grouping possibilities, and for each possibility, determine whether it satisfies the two conditions above (each matchstick belongs to one group, and the total length of matchsticks in each group is the same). Search each matchstick in order. When searching the ith matchstick, consider putting it into any one of the four groups. For each placement, continue DFS on the i + 1th matchstick. After we finish searching all N matchsticks, determine whether the sum of the lengths of each group is the same.

Code

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
}