package main

import (
	"fmt"
	"sort"
)

// 回溯递归+ 剪枝，依然超时，看来动态规划不只是回溯解空间的单纯剪枝，就背包问题来说还可以达到更好的优化程度
// 因为
func canPartition(nums []int) bool {
	n := len(nums)
	target := 0
	for _, v := range nums {
		target += v
	}
	if target%2 != 0 {
		return false
	}
	sort.Ints(nums)
	sum := 0
	flag := false
	visted := make(map[int]bool)
	var backtrace func(idx int)
	backtrace = func(idx int) {
		if idx > n {
			return
		}
		if visted[sum] {
			return
		}
		visted[sum] = true
		if sum == target/2 || flag {
			flag = true
			return
		}
		for i := idx; i < n; i++ {
			sum += nums[i]
			if visted[sum] || sum > target/2 {
				sum -= nums[i]
				continue
			}
			backtrace(i + 1)
			sum -= nums[i]
		}
	}
	backtrace(0)
	return flag
}

func main() {
	fmt.Println((canPartition([]int{1, 5, 11, 5})))
	fmt.Println(canPartition([]int{1, 2, 3, 5}))
	fmt.Println(canPartition([]int{100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 99, 97}))
	fmt.Println(canPartition([]int{14, 9, 8, 4, 3, 2}))
}