377.combination-sum-iv.md

377. Combination Sum IV

Key Insights

• It counts the number of permutations that can combine to target, so (2, 1, 1) and (1, 2, 1) are different.
• It's not about the actual combination, just counting them.
• 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 // Or we can skip the negative cases

// 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]!!
}

// Or equivalently, we check if num <= target, if so, we can add it to the combinations
private fun topDown(nums: IntArray, target: Int, memo: HashMap<Int, Int>): Int {
    if (target == 0) {
        return 1
    }
    // Here we don't check if target < 0, because we check num <= target in the for loop
    if (target !in memo) {
        var count = 0
        for (num in nums) {
            // We only add it to the combinations if num <= target
            if (num <= target) {
                count += sum(nums, target - num, memo)
            }
        }
        memo[target] = count
    }
    return memo[target]!!
}

Bottom-Up DP

Let dp[i] = the number of ways to sum to i. We can build up results for each target sum from 1 to target, so we iterate each target sum, then for each target sum, we iterate each num in nums as nested loop.

This order matters, it's used to count permutations, not just combinations.

To make sum i, try putting each num to the end of the combination, and see how many ways there are to from i - num.

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

private fun bottomUp(nums: IntArray, target: Int): Int {
    val dp = IntArray(target + 1)
    dp[0] = 1 // Base case: target == 0, we have 1 way to form it: use nothing
    for (i in 1..target) {
        for (num in nums) {
            if (num <= i) {
                dp[i] += dp[i - num]
            }
        }
    }
    return dp[target]
}

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

Dry Run

dp[0] = 1

dp[1] = dp[0] (using 1) + dp[-1] (skip)
       = 1

dp[2] = dp[1] (using 1) + dp[0] (using 2)
       = 1 + 1 = 2

dp[3] = dp[2] (using 1) + dp[1] (using 2)
       = 2 + 1 = 3

Combinations:
[1,1,1]
[1,2]
[2,1]