416.partition-equal-subset-sum.md

416. Partition Equal Subset Sum

• For the array that can be partitioned into two subsets with the same sum, it guarantees that the sum of subsets is the half of the sum from all elements.
• Then it becomes the 0/1 knapsack problem.

Dynamic Programming

fun canPartition(nums: IntArray): Boolean {
    if (nums.size == 1) return false

    var sum = 0
    for (num in nums) {
        sum += num
    }
    if (sum % 2 != 0) return false
    val target = sum / 2

    // val memo = hashMapOf<Pair<Int, Int>, Boolean>()
    // return knapsackTopDownDp(nums, target, nums.size, memo)
    return bottomUp1D(nums, target)
}

// Top-Down Memorization
private fun knapsack(nums: IntArray, target: Int, i: Int, memo: HashMap<Pair<Int, Int>, Boolean>): Boolean {
    if (target == 0) return true
    if (i == 0) return false

    if (memo.containsKey(target to i)) return memo[target to i]!!
    val skip = knapsack(nums, target, i - 1, memo)
    if (nums[i - 1] > target) memo[target to i] = skip
    else memo[target to i] = knapsack(nums, target - nums[i - 1], i - 1, memo) || skip
    return memo[target to i]!!
}

private fun bottomUp(nums: IntArray, target: Int): Boolean {
    val dp = Array(nums.size + 1) { _ -> BooleanArray(target + 1) }
    dp[0][0] = true
    for (i in 1..nums.size) {
        dp[i][0] = true
    }
    for (t in 1..target) {
        dp[0][t] = false
    }
    for (i in 1..nums.size) {
        for (t in 1..target) {
            if (nums[i - 1] > t) dp[i][t] = dp[i - 1][t]
            else dp[i][t] = dp[i - 1][t - nums[i - 1]] || dp[i - 1][t]
        }
    }
    return dp[nums.size][target]
}

private fun bottomUp1D(nums: IntArray, target: Int): Boolean {
    val dp = BooleanArray(target + 1)
    dp[0] = true
    for (i in 1..nums.size) {
        for (t in target downTo nums[i - 1]) {
            dp[t] = dp[t] || dp[t - nums[i - 1]]
        }
    }
    return dp[target]
}

Nice Mock Interview