题目

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

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

示例 1：

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

示例 2：

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

提示：

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

  • 1 <= target <= 1000


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

    解题方法

    动态规划

    与 518. 零钱兑换 II 不同的在于，本题求解组合数，所以需要交换内外循环顺序，在外循环遍历背包，内循环遍历物体
    时间复杂度O(target×l)，空间复杂度O(target)
    C++代码：

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

    进阶问题

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

例如，假设数组 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 的排列，就能构造出无限长度的排列。

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