leetcode-go/leetcode/medium/473.matchsticks-to-square.go

func makesquare(nums []int) bool {
	n := len(nums)
	if n < 4 {
		return false
	}
	sum := 0
	for _, i := range nums {
		sum += i
	}
	if sum%4 != 0 {
		return false
	}
	sort.Sort(sort.Reverse(sort.IntSlice(nums))) // It's super effective!
	return dfs(nums, make([]int, 4), n, 0, sum/4)
}

func dfs(nums []int, sums []int, n int, idx int, target int) bool {
	if idx == n {
		return sums[0] == target && sums[1] == target && sums[2] == target
	}
	for i := 0; i < 4; i++ {
		if sums[i]+nums[idx] <= target {
			sums[i] += nums[idx]
			if dfs(nums, sums, n, idx+1, target) {
				return true
			}
			sums[i] -= nums[idx]
		}
	}
	return false
}