题目：组合总和 Ⅳ

• 给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

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

进阶：

• 如果给定的数组中含有负数会怎么样？
• 问题会产生什么变化？
• 我们需要在题目中添加什么限制来允许负数的出现？

来源：力扣（LeetCode）第377题

链接：https://leetcode-cn.com/problems/combination-sum-iv

分析：

• dp和dfs两种方法。

代码：

• dp

  class Solution {
  public int combinationSum4(int[] nums, int target) {
      int len = nums.length;
      int[] dp = new int[target+1];
      dp[0] = 1;
      for (int i = 1; i <= target; i++) {
          for (int num : nums) if (i >= num) dp[i] += dp[i-num];
      }
      return dp[target];
  }
  }
  

• dfs + 记忆化

• 另外强调这种方法用java会超时，用c++要注意不要把数组初始化为0，就用数组的原数。

  class Solution {
  public:
  int len;
  int* memo;
  int combinationSum4(vector<int>& nums, int target) {
      len = nums.size();
      memo = new int[target];
      return dfs(nums, 0, target);
  }
  int dfs(vector<int>& nums, int sum, int target) {
      if (sum == target) return 1;
      if (sum > target) return 0;
      if (memo[sum] != -1094795586) return memo[sum];
      int ans = 0;
      for (int i = 0; i < len; i++) 
          ans += dfs(nums, sum + nums[i], target);
      memo[sum] = ans;
      return ans;
  }
  };