377. 组合总和 Ⅳ - Kotlin 背包DP

原题地址：https://leetcode.cn/problems/combination-sum-iv/description/

题解

反向题目：518. 零钱兑换 II

对于背包问题而言

• 外层遍历背包，内层遍历物品，最终结果为排列情况
• 外层遍历物品，内层遍历背包，最终结果为组合情况

时间复杂度：O(N^2)

空间复杂度：O(N)

class Solution {
    fun combinationSum4(nums: IntArray, target: Int): Int {
        val dp = IntArray(target + 1) { 0 }
        dp.forEachIndexed { i, _ ->
            nums.forEach { item ->
                if (i == 0) dp[i] = 1 else if (i - item >= 0) dp[i] += dp[i - item]
            }
        }
        return dp[target]
    }
}