LeetCode/kt/partition-equal-subset-sum.kt

class Solution {
    fun canPartition(nums: IntArray): Boolean {
        val total = nums.sum()
        if (total % 2 != 0) {
            return false
        }

        val target = total / 2
        val dp = BooleanArray(target + 1)

        dp[0] = true
        for (num in nums) {
            var current = target
            while (current >= num) {
                dp[current] = dp[current] || dp[current - num]
                if (dp[target]) {
                    return true
                }

                current--
            }
        }

        return dp[target]
    }
}