题解 | #八数码#

package main

import (
	"bufio"
	. "fmt"
	"io"
	"os"
	"sort"
)

var vis []bool

func dfs(a []int, currLen, currLine, targetLen, targetLine, j int) bool {
	if currLen > targetLen {
		return false
	} else if currLen == targetLen {
		j, currLen, currLine = 0, 0, currLine+1
	}
	if currLine == targetLine {
		return true
	}
	// 如果是尾部 则不用动这里的位置
	for i := j; i < len(a); i++ {
		if !vis[i] {
			vis[i] = true
			// 减枝3  i+1 由于是有序的所以往下看就好
			if dfs(a, currLen+a[i], currLine, targetLen, targetLine, i+1) {
				return true
			}
			vis[i] = false
			// 减枝1 头尾不对
			if currLen == 0 || currLen+a[i] == targetLen {
				return false
			}
			// 减枝2 相同长度的就不用试了
			for i < len(a)-1 && a[i] == a[i+1] {
				i++
			}
		}
	}
	return false
}

func NC50243(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()
	var n int
	Fscan(in, &n)
	a := make([]int, n)
	vis = make([]bool, n)
	max := 0
	total := 0
	for i := 0; i < n; i++ {
		Fscan(in, &a[i])
		total += a[i]
		if a[i] > max {
			max = a[i]
		}
	}
	sort.Slice(a, func(i, j int) bool { return a[i] > a[j] })
	for i := max; i <= total; i++ {
		if total%i == 0 {
			if dfs(a, 0, 0, i, total/i, 0) {
				Fprintln(out, i)
				break
			}
		}
	}
}

func main() {
	NC50243(os.Stdin, os.Stdout)
}