377. 组合总和 Ⅳ

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
输入：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)
请注意，顺序不同的序列被视作不同的组合。

复杂度分析

  • 时间复杂度：O(target×n)，其中 target 是目标值，nn 是数组 nums 的长度。需要计算长度为 target+1 的数组dp 的每个元素的值，对于每个元素，需要遍历数组 nums 之后计算元素值。

  • 空间复杂度：O(target)。需要创建长度为 target+1 的数组 dp。

    1. //完全背包问题，自顶向下=爬楼梯 == 
    2. //时间 O(mn)，m=target,n=len(nums);空间Om
    3. //其实是组合问题的特例=>排列问题
    4. func combinationSum4(nums []int, target int) int {
    5.   dp := make([]int ,target + 1)
    6.   dp[0] = 1
    8.   for i := 1; i <= target; i++ {      //amount 需要的钱大小,全排列问题，外层target
    10.       for _, num := range nums {      //内层nums
    11.           if i >= num {          //理解人肉压栈是不可能想出来滴
    12.               dp[i] += dp[i-num]     //核心，状态转移方程== 函数表达式
    13.           }
    14.       }
    15.   }
    16.   return dp[target]
    17. }