🚩传送门：https://leetcode-cn.com/problems/combination-sum-iv/

题目

给你一个由 不同 整数组成的数组 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

解题思路：动态规划

定义 表示选取的元素之和等于 的方案数，目标是求 。

动态规划的边界是 。当不选取任何元素时，元素之和为 0，因此只有 1 种方案 。

动态规划的做法：

  • 初始化 dp[0]=1；
  • 遍历 i 从 1 到 target，对于每个 i，进行如下操作
    • 遍历数组 nums 中的每个元素 num，当 num≤i 时，将 dp[i−num] 的值加到 dp[i] 。
  • 最终得到 dp[target] 的值即为答案 。

上述做法是否考虑到选取元素的顺序 ？
答案是肯定的。

因为外层循环是遍历从 1 到 target 的值，内层循环是遍历数组 nums 的值，在计算 dp[i] 的值时，nums 中的每个小于等于 i 的元素都可能作为元素之和等于 i 的排列的最后一个元素。

例如： 1 和 3 都在数组 nums 中，计算 dp[4] 的时候，排列的最后一个元素可以是 1 也可以是 3，因此 dp[1] 和 dp[3] 都会被考虑到，即不同的顺序都会被考虑到 。

状态转移方程：

复杂度分析

时间复杂度：，其中 [LeetCode]Dp377 组合总和 Ⅳ - 图1 为数组 [LeetCode]Dp377 组合总和 Ⅳ - 图2 的长度， 是目标值。

需要计算长度为 的数组 的每个元素的值，对于每个元素，需要遍历数组 之后计算元素值。

空间复杂度：，需要创建长度为 的数组 。

代码

官方代码

  1. class Solution {
  2.     public int combinationSum4(int[] nums, int target) {
  3.         int[] dp = new int[target + 1];
  4.         dp[0] = 1;
  5.         for (int i = 1; i <= target; i++) {
  6.             for (int num : nums) {
  7.                 if (num <= i) {
  8.                     dp[i] += dp[i - num];
  9.                 }
  10.             }
  11.         }
  12.         return dp[target];
  13.     }
  14. }

进阶问题

如果给定的数组中含有负数，则会导致出现无限长度的排列。

例如 假设数组 nums中含有正整数 a 和负整数 −b（其中 a>0,b>0,-b<0），则有 a×b+(−b)×a=0，对于任意一个元素之和等于 target 的排列，在该排列的后面添加 b 个 a 和 a 个 -b 之后，得到的新排列的元素之和仍然等于 target，而且还可以在新排列的后面继续 b 个 a 和 a 个 -b 。因此只要存在元素之和等于 target 的排列，就能构造出无限长度的排列。

如果允许负数出现，则必须限制排列的最大长度，避免出现无限长度的排列，才能计算排列数。