377.combination-sum-iv.md

377. Combination Sum IV

Key Insights

• It counts the number of combinations, so (2, 1, 1) and (1, 2, 1) are different.
• It's a classic counting problem: "count the number of ways to do something", a huge hint for DP. For the target, we can break it down into sub-problems: the number of combinations of target - nums[i]. And the combination is 1 when we reach 0 from target - nums[i]. (Similar to 518. Coin Change II, but order does not matter, counting the number of permutations, (2, 1, 1) and (1, 2, 1) are the same)

nums = [1, 2], target = 3

// Top-Down Recursive
f(3) =
    1 + f(2)
    2 + f(1)
f(2) =
    1 + f(1)
    2 + f(0)
f(1) =
    1 + f(0)
    2 + f(-1)

f(0) = 1
f(-1) = 0

// Backtracking
f(1) = 1 + 0 = 1
f(2) = 1 + 1 = 2
f(3) = 2 + 1 = 3

Top-Down DP

fun combinationSum4(nums: IntArray, target: Int): Int {
    val memo = HashMap<Int, Int>()
    return topDown(nums, target, memo)
}

private fun topDown(nums: IntArray, target: Int, memo: HashMap<Int, Int>): Int {
    // Base cases
    if (target == 0) return 1
    if (target < 0) return 0
    if (target !in memo) {
        var combinations = 0
        for (num in nums) {
            combinations += topDown(nums, target - num, memo)
        }
        memo[target] = combinations
    }
    return memo[target]!!
}

Bottom-Up DP

fun combinationSum4(nums: IntArray, target: Int): Int {
    return bottomUp(nums, target)
}

private fun bottomUp(nums: IntArray, target: Int): Int {
    val dp = IntArray(target + 1)
    // one way to form 0: use nothing
    dp[0] = 1
    for (t in 1..target) {
        for (num in nums) {
            if (t - num >= 0) {
                dp[t] += dp[t - num]
            }
        }
    }
    return dp[target]
}