educative.io

Alternate solution for Minimum Subset Sum Difference (hard)

Courses
,
#1

We can directly store the difference in the DP matrix

fun minimumDifferenceBetweenAnySubsetsDP(nums: IntArray): Int {
    val sum = nums.sum()

    val dp = Array(nums.size) { IntArray(sum / 2 + 1) { Int.MAX_VALUE } }
    dp.forEach { it[0] = sum } // difference between empty set and full set is the sum itself.

    for (s in 1..dp[0].lastIndex) {
        if (nums[0] <= s) {
            dp[0][s] = abs(nums[0] - (sum - nums[0]))
        }
    }

    for (i in 1..nums.lastIndex) {
        for (s in 1..dp[i].lastIndex) {
            if (nums[i] <= s) {
                dp[i][s] = min(abs(dp[i - 1][s - nums[i]] - 2 * nums[i]), dp[i - 1][s - nums[i]])
            }
            else {
                dp[i][s] = dp[i - 1][s]
            }
        }
    }

    return dp[nums.lastIndex][sum / 2]
}
1 Like