[LeetCode] 377. Combination Sum IV

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The answer is guaranteed to fit in a 32-bit integer.

Example 1:

Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.

Example 2:

Input: nums = [9], target = 3
Output: 0

Constraints:

1 <= nums.length <= 200
1 <= nums[i] <= 1000
All the elements of nums are unique.
1 <= target <= 1000

Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?

组合总和IV。

题意是给一个不存在重复数字的数组和一个正整数target，请你返回有多少种组合可以满足数组中间的数字的加和可以等于target。返回组合的数量。

乍一看这道题可以用递归做。比如题目中的例子，

nums = [1, 2, 3]
target = 4

因为数字可以重复使用，所以当发现target为4的时候，往下递归的第二层可以是1,2,3之间的任意一个数字；同理，再往下一层，又是可以用这三个数字。每往下一层，递归需要判断的条件都有三个。这种做法在遇到比如target number非常大但是nums里面的数字非常小的时候会很容易超时。优化的思路是用动态规划，来记录中间累加的结果。我这里介绍两种动态规划。

首先还是一个基于记忆化递归的动态规划。依然需要一个 dp[] 数组来记录中间结果。数组的长度是 target + 1（多预留一个位置给0，这是大部分DP数组创建的一个常识）。在遍历 nums 数组的时候，如果 target - nums[i] < 0，则不需要再往下递归了，肯定是错的；只有 target - nums[i] >= 0 的时候，再往下递归才有意义。递归的同时记录所有的中间结果。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     private int[] dp;
 3 
 4     public int combinationSum4(int[] nums, int target) {
 5         dp = new int[target + 1];
 6         Arrays.fill(dp, -1);
 7         dp[0] = 1;
 8         return helper(nums, target);
 9     }
10 
11     private int helper(int[] nums, int target) {
12         if (dp[target] != -1) {
13             return dp[target];
14         }
15         int res = 0;
16         for (int i = 0; i < nums.length; i++) {
17             if (target >= nums[i]) {
18                 res += helper(nums, target - nums[i]);
19             }
20         }
21         dp[target] = res;
22         return res;
23     }
24 }

另外一种思路就是纯粹的动态规划。这个方法有点类似coin change 2，每种硬币可以无限次使用的感觉。这里我也创建一个DP数组，数组的含义是对于一个target value，可以构建的组合有多少。其余部分请参见代码注释。

但是这道题跟518题的区别在于，377题给的其实是permutation，因为中间其实是有重复的解的（例子中已经标注红色）。但是518题是对于某一个给定的amount，只给了一种“有序的”解，不会出现类似5 = 1 + 1 + 3和5 = 1 + 3 + 1这种“重复”的解。所以本题的做法如果直接套用到518题是不对的。

时间O(n)

空间O(n)

Java实现

 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             // 对于每一个数字都去试试看
 7             for (int num : nums) {
 8                 // 如果当前target减去某一个值之后还大于0，则把减去的结果的DP值累加到当前这个target的DP值上
 9                 if (i - num >= 0) {
10                     dp[i] += dp[i - num];
11                 }
12             }
13         }
14         return dp[target];
15     }
16 }