494.target-sum.md

494. Target Sum

The problem f([2, 2], target = 0) can be break down into

• f([2], target = 2) (Use first 2 as positive)
• f([2], target = -2) (Use first 2 as negative)

And f([2], target = 2) can be break down into

• f([], target = 0) (Use first 2 as positive, again)
• f([], target = -2) (As same as above)

For f([], target = 0), there is one expression, and for f([], target = -2), there is no expression that can build to target, so it's zero. (This two are our base cases)

Backtracking

private var count = 0

fun findTargetSumWays(nums: IntArray, target: Int): Int {
    dfs(nums, target, nums.size - 1, 0)
    return counzt
}

private fun dfs(nums: IntArray, target: Int, index: Int, sum: Int) {
    if (index < 0) {
        if (target == sum) count++
    } else {
        // search positive number case
        dfs(nums, target, index - 1, sum + nums[index])

        // search negative number case
        dfs(nums, target, index - 1, sum - nums[index])
    }
}

Top-Down DP

It's similar to backtracking solution.

fun findTargetSumWays(nums: IntArray, target: Int): Int {
    // (target to i-size) to number of expression
    // NOTE!!! We can't use static array because the sum might be out of bound.
    val memo = hashMapOf<Pair<Int, Int>, Int>()
    return topDown(nums, target, nums.size, memo)
}

private fun topDown(nums: IntArray, target: Int, i: Int, memo: HashMap<Pair<Int, Int>, Int>): Int {
    if (target == 0 && i == 0) return 1
    if (i == 0) return 0
    if (memo.containsKey(target to i)) return memo[target to i]!!
    val positive = topDown(nums, target - nums[i - 1], i - 1, memo)
    val negative = topDown(nums, target + nums[i - 1], i - 1, memo)
    memo[target to i] = positive + negative
    return memo[target to i]!!
}

• Time Complexity: O(n * t) where n is the size of nums, and t is target.
• Space Complexity: O(n * t).

Nice explanation: https://leetcode.com/problems/target-sum/discuss/455024/DP-IS-EASY!-5-Steps-to-Think-Through-DP-Questions.

Bottom-Up DP

It's a knapsack variation problem, we must add all items into knapsack and see if the sum is the target.

For (i - 1)-th sum, we can add or substract the i-th number and see if the sum is the target value.

Because the target is not alway positive, we can't iterate from 0 to target from bottom-up. We have to transform this problem into other variation of knapsack problem. Suppose the S is the sum of all numbers in num, we have some numbers marked as positive (pos) and some as negative (neg), for pos and neg are some positive number, such that:

pos + neg = S
pos - neg = target

Then neg is = (S - target) / 2, and we are going to find if we can find the sum of number is equal to neg, it becomes the knapsack variation problem, the knapsack is neg and we try to find all the positive items that sum up to neg (we don't have to consider if the number to be positive or negative, here are all positive).

For example, [1, 1, 1, 1, 1] and target is 3, then the pos and neg will be

4 + 1 = S = 5
4 - 1 = target = 3

We're going to look for neg = 1, there are 5 1.

fun findTargetSumWays(nums: IntArray, target: Int): Int {
    var sum = 0
    for (num in nums) sum += num

    val diff = sum - target
    if (diff % 2 != 0 || diff < 0) return 0
    val neg = diff / 2
    val dp = Array(nums.size + 1) { _ -> IntArray(neg + 1) }
    for (t in 0..neg) {
        dp[0][t] = if (t == 0) 1 else 0
    }
    for (i in 1..nums.size) {
        for (t in 0..neg) {
            dp[i][t] = dp[i - 1][t]
            if (t - nums[i - 1] >= 0) {
                dp[i][t] += dp[i - 1][t - nums[i - 1]]
            }
        }
    }
    return dp[nums.size][neg]
}

• Time Complexity: O(n * neg).
• Space Complexity: O(n * neg).

Bottom-Up DP (Space Optimization)

fun findTargetSumWays(nums: IntArray, target: Int): Int {
    var sum = 0
    for (num in nums) sum += num

    val diff = sum - target
    if (diff % 2 != 0 || diff < 0) return 0
    val neg = diff / 2
    val dp = IntArray(neg + 1)
    dp[0] = 1
    for (i in 1..nums.size) {
        for (t in neg downTo nums[i - 1]) {
            dp[t] = dp[t] + dp[t - nums[i - 1]]
        }
    }
    return dp[neg]
}

• Time Complexity: O(n * neg).
• Space Complexity: O(neg).