Function PartitionProblem

dynamic/partitionproblem.go:11–30

PartitionProblem checks whether the given set can be partitioned into two subsets such that the sum of the elements in both subsets is the same.

(nums []int)

// PartitionProblem checks whether the given set can be partitioned into two subsets
// such that the sum of the elements in both subsets is the same.
func PartitionProblem(nums []int) bool {
	sum := 0
	for _, num := range nums {
		sum += num
	}
	if sum%2 != 0 {
		return false
	}

	target := sum / 2
	dp := make([]bool, target+1)
	dp[0] = true

	for _, num := range nums {
		for i := target; i >= num; i-- {
			dp[i] = dp[i] || dp[i-num]
		}
	}
	return dp[target]
}