Golang. Leetcode 416. Partition Equal Subset Sum.go

func canPartition(nums []int) bool {
	sum := 0
	for _, v := range nums {
		sum += v
	}
	if sum%2 == 1 {
		return false
	}
	dp := make([]bool, sum+1)
	for k := range dp {
		dp[k] = false
	}
	dp[0] = true
	for _, v := range nums {
		//注意，这里是倒着循环，避免被覆盖
		for i := sum; i >= 0; i-- {
			if dp[i] {
				dp[i+v] = true
			}
		}
		if dp[sum/2] {
			return true
		}
	}
	return false
}