一、题目内容 中等

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

题目数据保证答案符合 32 位整数范围。

示例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) 请注意，顺序不同的序列被视作不同的组合。

示例2：

输入：nums = [9], target = 3 输出：0

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 1000
  • nums 中的所有元素 互不相同
  • 1 <= target <= 1000

    进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

二、解题思路

:::warning 本题题目描述说是求组合，但又说是可以元素相同顺序不同的组合算两个组合，其实就是求排列！ :::

但其本质是本题求的是排列总和，而且仅仅是求排列总和的个数，并不是把所有的排列都列出来。 如果本题要把排列都列出来的话，只能使用回溯算法爆搜。

动规五部曲分析如下：

  1. 确定dp数组以及下标的含义

**dp[i]**: 凑成目标正整数为 i 的排列个数为**dp[i]**

  1. 确定递推公式

dp[i]可以由 dp[i - nums[j]]推导出来。
因为只要得到nums[j]，排列个数dp[i - nums[j]]，就是dp[i]的一部分

  1. dp数组如何初始化

因为递推公式dp[i] += dp[i - nums[j]]的缘故，dp[0] 要初始化为 1，这样递归其他dp[i]的时候才会有数值基础。

  1. 确定遍历顺序

个数可以不限使用，说明这是一个完全背包。
得到的集合是排列，说明需要考虑元素之间的顺序。
本题要求的是排列，那么这个 for 循环嵌套的顺序可以有说法了。 :::info 如果求组合数就是外层 for 循环遍历物品，内层 for 遍历背包。
如果求排列数就是外层 for 遍历背包，内层 for 循环遍历物品。 ::: 如果把遍历 nums（物品）放在外循环，遍历 target 的作为内循环的话，举一个例子：计算dp[4]的时候，结果集只有 {1,3} 这样的集合，不会有{3,1}这样的集合，因为 nums 遍历放在外层，3 只能出现在 1 后面！
所以本题遍历顺序最终遍历顺序：target（背包）放在外循环，将nums（物品）放在内循环，内循环从前到后遍历。

  1. 举例来推导 dp 数组

image.png

三、具体代码

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} target
  4.  * @return {number}
  5.  */
  6. var combinationSum4 = function (nums, target) {
  7.   const dp = new Array(target + 1).fill(0)
  8.   dp[0] = 1
  9.   for (let j = 0; j <= target; j++) {
  10.     for (let i = 0; i < nums.length; i++) {
  11.       if (j >= nums[i]) dp[j] += (dp[j - nums[i]] || 0)
  12.     }
  13.   }
  14.   return dp[target]
  15. };

四、其他解法