package main

import (
	"fmt"
	"math"
	"sort"
)

func numberOfWeeks(milestones []int) int64 {
	// 1.排序 2.回溯找最近二分点
	sort.Slice(milestones, func(i, j int) bool {
		return milestones[i] > milestones[j]
	})
	n := len(milestones)
	sum := 0
	for _, v := range milestones {
		sum += v
	}
	trace := 0
	res := math.MaxInt32
	var dfs func(idx int)
	dfs = func(idx int) {
		if idx > n {
			return
		}
		if trace > sum/2 {
			return
		}
		res = min(res, sum/2-trace)
		for i := idx; i < n; i++ {
			trace += milestones[i]
			dfs(i + 1)
			trace -= milestones[i]
		}
	}
	dfs(0)
	res = sum/2 - res
	if res == int(math.Ceil(float64(sum)/2)) {
		return int64(res * 2)
	}
	return int64(res*2) + 1
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	//fmt.Println(numberOfWeeks([]int{1, 2, 3}))
	//fmt.Println(numberOfWeeks([]int{5, 2, 1}))
	//fmt.Println(numberOfWeeks([]int{9, 3, 6, 8, 2, 1}))
	fmt.Println(numberOfWeeks([]int{5, 7, 5, 7, 9, 7}))
}