题目

给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

题解

只要看到目标值、数组、选择，这三要素，就直接可以反应想到是背包问题。

这里数组中的元素是可以重复选取的，所以是完全背包问题。

大的target可以拆解为小target加一系列选择求解，所以要遍历所有的target取值可能，还要遍历所有数字取值可能，有两层循环。

这里要注意顺序不同的序列被视作不同的组合，这涉及到双层循环的哪一个循环应该放在外层。
由于不锁定数字选择顺序，nums数组遍历应该放在内层，这样target才可以由不同顺序的选择得到。
如果nums数组遍历放在外层，会锁定nums数组的选取顺序，一个target只会有一种顺序的选择得到。
这与LeetCode.518.零钱兑换 II（中等）情况正好相反。

class Solution {
    fun combinationSum4(nums: IntArray, target: Int): Int {
        val n = nums.size
        val dp = IntArray(target + 1) { 0 }
        dp[0] = 1
        for (t in 0..target) {
            for (num in nums) {
                if (t >= num) {
                    dp[t] += dp[t - num]
                }
            }
        }
        return dp[target]
    }
}

Ricky.L的随笔

LeetCode.377.组合总和 Ⅳ（中等）

题目

题解