Leetcode - partition-equal-subset-sum

https://leetcode.com/problems/partition-equal-subset-sum/

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

1. Each of the array element will not exceed 100.
2. The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

func canPartition(nums []int) bool {
    if len(nums) == 0 {
        return false
    }
    sum := 0
    for _, n := range nums {
        sum += n
    }
    if sum % 2 == 1 {
        return false
    }
    subSum := sum / 2
    dp := make([][]bool, subSum+1)
    for i := 0; i <= subSum; i++{
        dp[i] = make([]bool, len(nums)+1)
    }
    dp[0][0] = true
    for i := 1; i <= subSum; i++ {
        dp[i][0] = false
    }
    for j := 1; j <= len(nums); j++ {
        dp[0][j] = true
    }
    for i := 1; i <= subSum; i++ {
        for j := 1; j <= len(nums); j++ {
            if i - nums[j-1] >= 0 {
                dp[i][j] = dp[i][j-1] || dp[i-nums[j-1]][j-1]
            }
        }
    }
    
    return dp[subSum][len(nums)]
}

• 相关文章
• 全局相关文章